direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

The Power of Compromise
Zitatschlüssel Report-025-2012
Autor Christina Büsing and Kai-Simon Goetzmann and Jannik Matuschke and Sebastian Stiller
Seiten 15 pages
Jahr 2012
Nummer 025
Institution TU Berlin
Zusammenfassung We study a concept in multicriteria optimization called compromise solutions (introduced in 1973 by Yu) and a generalized version of this, termed reference point solutions. Our main result shows the power of this concept: Approximating reference point solutions is polynomially equivalent to constructing an approximate Pareto set as defined by Papadimitriou and Yannakakis in 2000. A reference point solution is the solution closest to a given reference point in the objective space. Compromise solutions use the component-wise minimum over all solutions as a reference point. These methods are widely spread in practice. While for a fixed norm it gives a single solution balancing the different criteria, by changing the norm in the objective space each point in the Pareto set can become the reference point solution, thus maintaining the full variability of multicriteria problems. Despite its apparent virtues only few theoretical and even less algorithmic results are known for reference point methods. We study minimization problems with a constant number of criteria. In addition to the equivalence of approximability of reference point solutions and the Pareto set, our techniques allow us to show that the Pareto set has a constant factor approximation if and only if the single-criteria problem has a constant factor approximation. We further give several general techniques to obtain solutions for reference point methods. The main algorithmic result is an LP-rounding technique that achieves the same approximation factors for reference point solutions as in the single-criteria case for many classical combinatorial problems, including set-cover and several machine scheduling problems. By the established link our algorithmic results also give a short alternative proof for the existence of an FPTAS of the Pareto set in the case of linear optimization over convex sets [Papadimitriou&Yannakakis,2000].
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag