### Samenvatting

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.

Originele taal-2 | Engels |
---|---|

Titel | Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers |

Redacteuren | K. Jansen, M. Mastrolilli |

Plaats van productie | Cham |

Uitgeverij | Springer |

Pagina's | 92-102 |

Aantal pagina's | 11 |

ISBN van elektronische versie | 978-3-319-51741-4 |

ISBN van geprinte versie | 978-3-319-51740-7 |

DOI's | |

Status | Gepubliceerd - 2017 |

Evenement | 14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denemarken Duur: 25 aug 2016 → 26 aug 2016 Congresnummer: 14 http://conferences.au.dk/algo16/waoa/ http://conferences.au.dk/algo16/travel-and-local-information/ |

### Publicatie series

Naam | Lecture Notes in Computer Science |
---|---|

Volume | 10138 |

ISSN van geprinte versie | 0302-9743 |

ISSN van elektronische versie | 1611-3349 |

### Congres

Congres | 14th International Workshop on Approximation and Online Algorithms (WAOA 2016) |
---|---|

Verkorte titel | WOA 2016 |

Land | Denemarken |

Stad | Aarhus |

Periode | 25/08/16 → 26/08/16 |

Internet adres |

## Vingerafdruk Duik in de onderzoeksthema's van 'Balanced optimization with vector costs'. Samen vormen ze een unieke vingerafdruk.

## Citeer dit

*Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers*(blz. 92-102). (Lecture Notes in Computer Science ; Vol. 10138). Springer. https://doi.org/10.1007/978-3-319-51741-4_8