June 26, 2001

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.