Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
8971

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V