• search hit 211 of 1103
Back to Result List

Compromise Solutions in Multicriteria Combinatorial Optimization

Please always quote using this URN:urn:nbn:de:0296-matheon-10236
  • 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 coor- dinates 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 � ts 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 so- lution 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christina Büsing
URN:urn:nbn:de:0296-matheon-10236
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/02/02
Release Date:2012/02/02
Tag:Approximation; Compromise Solutions; Multicriteria Combinatorial Optimization; Pareto Optimality
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-06 Proceedings, conferences, collections, etc.
Preprint Number:912
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.