On the inapproximability of the metric traveling salesman problem

One of the central tasks in combinatorial optimization is to classify the NP-hard optimization problems according to their approximability. One of the best-known and most important optimization problems is the traveling salesman problem (TSP). In this thesis we consider the metric traveling salesman problem, i.e. the special case of the TSP where the edge costs obey the triangle inequality. Under the assumption P not equal NP we will prove a lower bound of 3813/3812 - epsilon on the polynomial-time approximability of the metric TSP for an arbitrary small epsilon > 0. This improves over the previously known lower bound of 5381/5380 - epsilon (for an arbitrary small epsilon > 0) that was proved by Engebretsen [En99]. Engebretsen used a gap-preserving reduction from a problem about linear equations, the so-called LinEq2-2(3) problem, to the subproblem of the TSP where all edge costs are equal to 1 or 2. We generalize this proof method and consider a reduction from LinEq2-2(3) to those Delta-TSP instances where all edge costs are from {1,2,3}. This modification requires essential changes in the construction of Engebretsen and several new technical considerations. Furthermore we apply our proof method to derive lower bounds on the approximability of the TSP with parameterized triangle inequality.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2000

Author dc:creator

• Böckenhauer, Hans-Joachim

Contributors dc:contributor

• Hromkovic, Juraj

• info:eu-repo/classification/ddc/004
• Informatik
• Travelling-salesman-Problem
• Approximation

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123535%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:61923