Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2006 Copyright 2006 University of Bonn, Department of Computer Science, Abt. V
85273

09.02.2006

TSP with Bounded Metrics
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 bounded metrics,i.e., metrics where the distances are integers betweenone and some constant upper bound. In this case, the problem isknown to be approximable within a constant factor. We prove that itis NP-hard to approximate the asymmetric TSP with distances one andtwo within 321/320 - ε and that it is NP-hard toapproximate the symmetric TSP with distances one and two within741/740 - ε for every constant ε > 0.
Recently, Papadimitriou and Vempala announced improved approximationhardness results for both symmetric and asymmetric TSP with graph metric.We show that a similar construction can be used to obtain only slightlyweaker approximation hardness results for TSP with triangle inequality anddistances that are integers between one and eight. This shows that thePapadimitriou-Vempala construction is

Last Change: 11/05/14 at 10:37:10
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V