Abstract
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 language | English |
---|---|
Title of host publication | Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers |
Editors | K. Jansen, M. Mastrolilli |
Place of Publication | Cham |
Publisher | Springer |
Pages | 92-102 |
Number of pages | 11 |
ISBN (Electronic) | 978-3-319-51741-4 |
ISBN (Print) | 978-3-319-51740-7 |
DOIs | |
Publication status | Published - 2017 |
Event | 14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denmark Duration: 25 Aug 2016 → 26 Aug 2016 Conference number: 14 http://conferences.au.dk/algo16/waoa/ http://conferences.au.dk/algo16/travel-and-local-information/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 10138 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 14th International Workshop on Approximation and Online Algorithms (WAOA 2016) |
---|---|
Abbreviated title | WOA 2016 |
Country/Territory | Denmark |
City | Aarhus |
Period | 25/08/16 → 26/08/16 |
Internet address |
Funding
This research has been supported by the Netherlands Organisation for Scientific Research (NWO) under Grant 639.033.403, by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society), and by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office.
Keywords
- Approximation
- Assignment problem
- Balanced optimization
- Computational complexity