Treffer: Approximation Algorithms for Combinatorial Multicriteria Optimization Problems

The computational complexity of combinatorial multiple objective programming problems is investigated. INP -completeness and #P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well known tree and Christofides' heuristics for the TSP is investigated in the multicriteria case with respect to the two definitions of approximability. Keywords: Multicriteria Optimization, Combinatorial Optimization, INP -completeness, Approximation Algorithms AMS subject classification: 90C29, 90C27 1 Introduction In this paper we will study combinatorial optimization problems with multiple criteria. Interest in multicriteria optimization (or multiple objective programming, MOP) with respect to theory and applications has been growing in recent years, as can be seen from the literature reviews in [32, 39]. The reason for this is certainly that in real world problems almost.