
University of Bonn > Department of Computer Science > Chair V  
CSAPXReports 2004  Copyright 2004 University of Bonn, Department of Computer Science, Abt. V  
8994 10.1.2005 
TSP with Bounded Metrics: Approximation Hardness for the (1,2) Case
Lars Engebretsen and Marek Karpinski [Download PostScript] [Download PDF] The general asymmetric TSP with triangle inequality is known to be approximableonly within logarithmic factors. In this paper we study the asymmetricand symmetric TSP problems with bounded metrics, i.e., metrics where the distancesare integers between one and some constant upper bound. In this case, the problemis known to be approximable within a constant factor. We prove that it is NPhardto approximate the asymmetric TSP with distances one and two within 321/320εand that it is NPhard to approximate the symmetric TSP with distances one and twowithin 741/740ε for every constant ε > 0. 

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