TY - GEN A1 - Büsing, Christina T1 - Compromise Solutions in Multicriteria Combinatorial Optimization N2 - 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. KW - Multicriteria Combinatorial Optimization KW - Compromise Solutions KW - Pareto Optimality KW - Approximation Y1 - 2012 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1023 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-10236 ER -