Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2004 Copyright 2004 Universität Bonn, Institut für Informatik, 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 NP-hardto approximate the asymmetric TSP with distances one and two within 321/320-εand that it is NP-hard 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V