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