## 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 | Denmark |

City | Aarhus |

Period | 25/08/16 → 26/08/16 |

Internet address |

## Keywords

- Approximation
- Assignment problem
- Balanced optimization
- Computational complexity