On the inapproximability of the metric traveling salesman problem

Böckenhauer, Hans-Joachim; Hromkovic, Juraj

doi:57

On the inapproximability of the metric traveling salesman problem

Böckenhauer, Hans-Joachim (Author)

2000

Verantwortlichkeitsangabevorgelegt von Hans-Joachim Böckenhauer

ImpressumAachen : Publikationsserver der RWTH Aachen University 2000

Umfang103 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2000

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Hromkovic, Juraj (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2000-09-18

Online
URN: urn:nbn:de:hbz:82-opus-574
URL: https://publications.rwth-aachen.de/record/61923/files/Boeckenhauer_Hans-Joachim.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; Travelling-salesman-Problem (frei) ; Approximation (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Eine zentrale Aufgabe der kombinatorischen Optimierung ist die Klassifizierung von NP-schweren Optimierungsproblemen nach ihrer Approximierbarkeit. Eines der bekanntesten und wichtigsten Optimierungsprobleme ist das Traveling-Salesman-Problem (TSP). In dieser Dissertation betrachten wir das metrische Traveling-Salesman-Problem, d.h. den Spezialfall des TSP, bei dem alle Kantenkosten die Dreiecksungleichung erfüllen. Unter der Voraussetzung P ungleich NP erhalten wir für das Delta-TSP eine untere Schranke für die Polynomialzeit-Approximierbarkeit von 3813/3812 - epsilon (für ein beliebig kleines epsilon > 0). Dies ist eine Verbesserung gegenüber der bisher bekannten unteren Schranke von 5381/5380 - epsilon (für ein beliebig kleines epsilon > 0), die von Engebretsen bewiesen wurde [En99]. Engebretsen verwendete eine lückenerhaltende Reduktion von einem Problem über lineare Gleichungen, dem sogenannten LinEq2-2(3)-Problem, auf das TSP-Teilproblem, bei dem alle Kantenkosten gleich 1 oder 2 sind. Wir verallgemeinern diese Beweistechnik und betrachten eine Reduktion von LinEq2-2(3) auf solche Delta-TSP-Instanzen, bei denen alle Kantenkosten aus {1,2,3} sind. Diese Modifikation macht es erforderlich, die Konstruktion von Engebretsen wesentlich zu ändern, und es sind einige neue, zusätzliche technische Betrachtungen notwendig. Weiterhin wenden wir unsere Beweismethode an, um untere Schranken für die Approximierbarkeit des TSP mit parametrisierter Dreiecksungleichung zu erhalten.

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.

OpenAccess:
PDF
(additional files)