Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR00-089 | 9th September 2001 00:00

Approximation Hardness of TSP with Bounded Metrics Revision of: TR00-089

RSS-Feed




Revision #1
Authors: Lars Engebretsen, Marek Karpinski
Accepted on: 9th September 2001 00:00
Downloads: 1001
Keywords: 


Abstract:

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.


Paper:

TR00-089 | 1st December 2000 00:00

Approximation Hardness of TSP with Bounded Metrics





TR00-089
Authors: Lars Engebretsen, Marek Karpinski
Publication: 3rd December 2000 09:44
Downloads: 1052
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint