Open Collections

Description

We consider so-called balanced optimization problems with vector costs. We pro- pose a framework containing such problems; this framework allows us to investigate the complexity and approximability of these problems in a general setting. More concrete, each problem in the framework admits a 2-approximation, and for many problems within the framework this result is best-possible, in the sense that having a polynomial-time algorithm with a performance ratio better than 2 would imply P=NP. Special attention is paid to the balanced assignment problem with vector costs: we show that the problem remains NP-hard even in case of sum costs. This is joint work with Annette Ficker and Gerhard Woeginger