Robust balanced optimization

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
6 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)239-266
Number of pages28
JournalEURO Journal on Computational Optimization
Volume6
Issue number3
DOIs
Publication statusPublished - 1 Sep 2018

Keywords

  • Approximation
  • Assignment problem
  • Balanced optimization
  • Computational complexity

Fingerprint

Dive into the research topics of 'Robust balanced optimization'. Together they form a unique fingerprint.

Cite this