Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs
Open access
Author
Date
2011-06Type
- Master Thesis
ETH Bibliography
yes
Altmetrics
Abstract
We consider the beta-metric traveling salesman problem (Delta-beta-TSP), i.e., the TSP restricted to input instances satisfying the beta-triangle inequality c({v,w}) <= beta * (c{v,u} + c{u,w}), for any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) provides an approximation ratio of 3/2 * beta^2 and is the best known algorithm in the range 1 <= beta <= 2. We show that this upper bound is tight by providing a worst-case example. This example can also be used to show the tightness of the upper bound for the PMCA variants for the Hamiltonian path problem with zero and one prespecified endpoints. For two prespecified endpoints, we cannot reuse the example, but we construct another worst-case example to show the tightness of the upper bound also in this case. Furthermore, we establish improved lower bounds for an approximation algorithm for the metric Hamiltonian path problem as well as for two approximation algorithms for the metric TSP reoptimization problem. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006519144Publication status
publishedPublisher
Eidgenössische Technische Hochschule Zürich, Institute of Theoretical Computer Science, Chair of Information Technology and EducationSubject
Approximation algorithms; Reoptimization; PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; COMBINATORIAL PROBLEMS (DISCRETE PROGRAMMING); KOMBINATORISCHE PROBLEME (DISKRETE OPTIMIERUNG); Hamiltonian path problem; Traveling salesman problem; PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEMEOrganisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science
More
Show all metadata
ETH Bibliography
yes
Altmetrics