Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-51741-4_8 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Balanced optimization,Assignment problem,Computational complexity,Approximation | Combinatorics,Mathematical optimization,Computer science,Performance ratio,Generalized assignment problem,L-reduction,Assignment problem,Optimization problem,Computational complexity theory | Conference |
Volume | ISSN | Citations |
10138 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Annette M. C. Ficker | 1 | 2 | 1.70 |
| Frits C. R. Spieksma | 2 | 591 | 58.84 |
| Gerhard Woeginger | 3 | 4176 | 384.37 |