TU Berlin

Kai-Simon GoetzmannPublications & Talks

Page Content

to Navigation

Publications

Goetzmann, Kai-Simon and Stiller, Sebastian and Telha, Claudio.
Optimization over Integers with Robustness in Cost and Few Constraints.
In Solis-Oba, Roberto and Persiano, Giuseppe (ed.)Approximation and Online Algorithms (WAOA 2011), pp. 89-101, Springer Berlin / Heidelberg, 2012.



Preprints

The Power of Compromise
Citation key Report-025-2012
Author Christina Büsing and Kai-Simon Goetzmann and Jannik Matuschke and Sebastian Stiller
Pages 15 pages
Year 2012
Number 025
Institution TU Berlin
Abstract 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].
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Diploma Thesis

Kai-Simon Goetzmann
Robust Combinatorial Optimization.
Technische Universität Berlin, July 2010.
Supervisors: Rolf H. Möhring, Martin Skutella

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe