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.

Metadaten
Verfasser*innenangaben:	Matthias Ehrgott
URN:	urn:nbn:de:hbz:386-kluedo-4818
Schriftenreihe (Bandnummer):	Report in Wirtschaftsmathematik (WIMA Report) (39)
Dokumentart:	Preprint
Sprache der Veröffentlichung:	Englisch
Jahr der Fertigstellung:	1999
Jahr der Erstveröffentlichung:	1999
Veröffentlichende Institution:	Technische Universität Kaiserslautern
Datum der Publikation (Server):	03.04.2000
Freies Schlagwort / Tag:	Approximation Algorithms; Combinatorial Optimization; Multicriteria Optimization; NP-completeness
Fachbereiche / Organisatorische Einheiten:	Kaiserslautern - Fachbereich Mathematik
DDC-Sachgruppen:	5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):	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
Lizenz (Deutsch):	Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011