Department of Computer Science
 
Chair V

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

December 4, 2000

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

The general asymmetric (and metric) TSP 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 54/53 and 131/130, respectively, for these problems. 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 of Engebretsen for the case of distances one and two, by the order of magnitude. Furthermore, one of our constructions can be used to improve a recent lower bound of Papadimitriou and Vempala for the case of symmetric TSP with unbounded metric.

Last Change: 11/05/14 at 10:16:07
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V