December 4, 2000

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.