
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2006  Copyright 2006 Universität Bonn, Institut für Informatik, 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 NPhard to approximate the asymmetric TSP with distances one andtwo within 321/320  ε and that it is NPhard toapproximate the symmetric TSP with distances one and two within741/740  ε for every constant ε > 0. 

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