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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Author:Matthias Ehrgott
URN (permanent link):urn:nbn:de:hbz:386-kluedo-4818
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (39)
Document Type:Preprint
Language of publication:English
Year of Completion:1999
Year of Publication:1999
Publishing Institute:Technische Universität Kaiserslautern
Tag:Approximation Algorithms; Combinatorial Optimization ; Multicriteria Optimization ; NP-completeness
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):90C27 Combinatorial optimization
90C29 Multi-objective and goal programming

$Rev: 12793 $