Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2005 Copyright 2005 University of Bonn, Department of Computer Science, Abt. V
8996

16.02.2005

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V