Balanced optimization with vector costs

A.M.C. Ficker, F.C.R. Spieksma, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


An instance of a balanced optimization problem with vector costs consists of a ground set X, a vector cost for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the spread (or imbalance) of values in every coordinate of the underlying vector costs. We investigate the complexity and approximability of balanced optimization problems in a fairly general setting. We identify a large family of problems that admit a 2-approximation in polynomial time, and we show that for many problems in this family this approximation factor 2 is best-possible (unless P=NP). Special attention is paid to the balanced assignment problem with vector costs, which is shown to be NP-hard even in the highly restricted case of sum costs.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers
EditorsK. Jansen, M. Mastrolilli
Place of PublicationCham
Number of pages11
ISBN (Electronic)978-3-319-51741-4
ISBN (Print)978-3-319-51740-7
Publication statusPublished - 2017
Event14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denmark
Duration: 25 Aug 201626 Aug 2016
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th International Workshop on Approximation and Online Algorithms (WAOA 2016)
Abbreviated titleWOA 2016
Internet address


  • Approximation
  • Assignment problem
  • Balanced optimization
  • Computational complexity


Dive into the research topics of 'Balanced optimization with vector costs'. Together they form a unique fingerprint.

Cite this