### 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.

**Goetzmann, Kai-Simon**.

**The Power of Compromise. Reference Point Methods and Approximation in Multicriteria Optimization**.

Doctoral thesis, TU Berlin, 2013.

## Preprints

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 |

## Diploma Thesis

Kai-Simon Goetzmann

Robust Combinatorial Optimization.

Technische Universität Berlin, July 2010.

Supervisors: Rolf H. Möhring, Martin Skutella

## Talks & Workshops

Final presentation Diploma thesis, COGA-Seminar Sep 9, 2010:

Robust Combinatorial Optimization

Poster for assessment of the research training group MDS, October 2010:

Robust Combinatorial Optimization

Colloquium of the research training group MDS, Feb 7, 2011:

Multicriteria Optimization and Compromise Solutions

OR 2011 in Zurich, Aug 31, 2011:

Compromise Solutions

WAOA 2011 in Saarbrücken, Sept 8, 2011:

Optimization over Integers with Robustness in Cost and Few Constraints

ISAAC 2011 in Yokohama, Dec 7, 2011:

Optimal File Distribution in Peer-to-Peer Networks

Status workshop of the research training group MDS, Feb 11, 2012:

Compromise Solutions

SCOR 2012 in Nottingham, April 20, 2012:

Compromise Solutions

Colloquium of the research training group MDS, June 25, 2012:

Reference Point Methods and Approximation in Multicriteria Optimization

FRICO 2012 in Berlin, August 15, 2012:

The Power of Compromise

ISMP 2012 in Berlin, August 20, 2012:

Compromise Solutions and Approximation in Multicriteria Optimization

OR 2012 in Hannover, September 5, 2012:

Reference Point Methods and Approximation in Multicriteria Optimization