Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2001 Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V
85227

June 26, 2001

Approximation Hardness of TSP with Bounded Metrics (Revised Version)
Lars Engebretsen and Marek Karpinski
[Download PostScript] [Download PDF]

The general asymmetric TSP with triangle inequality is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics and prove approximation lower bounds of 131/130 and 174/173, respectively, for these problems, improving over the previous best lower bounds of 2805/2804 and 3813/3812 by an order of magnitude. Our bound 174/173 for the symmetric TSP with bounded metric is also the currently best known approximation lower bound for the general metric symmetric TSP problem.
We prove also approximation lower bounds of 321/320 and 743/742 for the asymmetric and symmetric TSP with distances one and two, improving over the previous best lower bounds of 2805/2804 and 5381/5380.

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

Powered by Zope