direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Compromise Solutions in Multicriteria Combinatorial Optimization
Zitatschlüssel Report-019-2011
Autor Christina Büsing and Kai-Simon Goetzmann and Jannik Matuschke
Seiten 27 pages
Jahr 2011
Nummer 019
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung In multicriteria optimization, a compromise solution is a feasible solution whose cost vector minimizes the distance to the ideal point w.r.t. a given norm. The coordinates of the ideal point are given by the optimal values for the single optimization problem for each criterion. We show that the concept of compromise solutions fits nicely into the existing notion of Pareto optimality: For a huge class of norms, every compromise solution is Pareto optimal, and under certain conditions on the norm all Pareto optimal solution are also a compromise solution, for an appropriate weighting of the criteria. Furthermore, under similar conditions on the norm, the existence of an FPTAS for compromise solutions guarantees the approximability of the Pareto set. These general results are completed by applications to classical combinatorial optimization problems. In particular, we study approximation algorithms for the multicriteria shortest path problem and the multicriteria minimum spanning tree problem. On the one hand, we derive approximation schemes for both problems, on the other hand we show that for the latter problem simple approaches like local search and greedy techniques do not guarantee good approximation factors.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag