Revision #1 Authors: Lars Engebretsen, Marek Karpinski

Accepted on: 9th September 2001 00:00

Downloads: 1571

Keywords:

The general asymmetric TSP with triangle inequality is known

to be approximable only 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, i.e., metrics where the distances are

integers between one and some upper bound B. We first prove

approximation lower bounds of 321/320 and 741/740 for the asymmetric

and symmetric TSP with distances one and two, improving over the

previous best lower bounds of 2805/2804 and 5381/5380. Then we

consider the TSP with triangle inequality and distances that are

integers between one and eight and prove approximation lower bounds of

131/130 for the asymmetric and 405/404 for the symmetric,

respectively, version of that problem, improving over the previous

best lower bounds of 2805/2804 and 3813/3812 by an order of magnitude.

TR00-089 Authors: Lars Engebretsen, Marek Karpinski

Publication: 3rd December 2000 09:44

Downloads: 1914

Keywords:

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.