|
Universität Bonn -> Institut für Informatik -> Abteilung V | ||
CS-Reports 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 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. |
|
Last Change:
11/05/14 at 10:37:10
English |
Universität Bonn -> Institut für Informatik -> Abteilung V |