### Samenvatting

An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost-vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vector costs. Balanced optimization problems with vector costs are equivalent to the robust optimization version of balanced optimization problems under the min-max criterion. We regard these problems as a family of optimization problems; one particular member of this family is the known balanced assignment problem. We investigate the complexity and approximability of robust 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). We pay special attention to the balanced assignment problem with vector costs and show that this problem is NP-hard even in the highly restricted case of sum costs. We conclude by performing computational experiments for this problem.

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

Pagina's (van-tot) | 239-266 |

Aantal pagina's | 28 |

Tijdschrift | EURO Journal on Computational Optimization |

Volume | 6 |

Nummer van het tijdschrift | 3 |

DOI's | |

Status | Gepubliceerd - 1 sep 2018 |

## Vingerafdruk Duik in de onderzoeksthema's van 'Robust balanced optimization'. Samen vormen ze een unieke vingerafdruk.

## Citeer dit

Ficker, A. M. C., Spieksma, F. C. R., & Woeginger, G. (2018). Robust balanced optimization.

*EURO Journal on Computational Optimization*,*6*(3), 239-266. https://doi.org/10.1007/s13675-018-0093-y