- search hit 1 of 1
Approximation Algorithms for Combinatorial Multicriteria Optimization Problems
- The computational complexity of combinatorial multiple objective programming problems is investigated. NP-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.
Author: | Matthias Ehrgott |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-4818 |
Series (Serial Number): | Report in Wirtschaftsmathematik (WIMA Report) (39) |
Document Type: | Preprint |
Language of publication: | English |
Year of Completion: | 1999 |
Year of first Publication: | 1999 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2000/04/03 |
Tag: | Approximation Algorithms; Combinatorial Optimization; Multicriteria Optimization; NP-completeness |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
MSC-Classification (mathematics): | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C29 Multi-objective and goal programming | |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |