Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2005 Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V


TSP with Bounded Metrics: Stronger Approximation Hardness
Lars Engebretsen and Marek Karpinski
[Download PostScript] [Download PDF]

The general asymmetric TSP with triangle inequality is known to beapproximable only within logarithmic factors. In this paper we studythe asymmetric and symmetric TSP problems with boundedmetrics, i.e., metrics where the distances are integers betweenone and some constant upper bound. Recently, Papadimitriou andVempala announced improved approximation hardness results for bothsymmetric and asymmetric TSP with graph metric. In this note, weshow that a similar construction can be used to obtain only slightlyweaker approximation hardness results for TSP with triangleinequality and distances that are integers between one andeight. This shows that the Papadimitriou-Vempala construction is

Last Change: 11/05/14 at 10:33:19
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope