ECCC-Report TR00-089https://eccc.weizmann.ac.il/report/2000/089Comments and Revisions published for TR00-089en-usSun, 09 Sep 2001 00:00:00 +0300
Revision 1
| Approximation Hardness of TSP with Bounded Metrics Revision of: TR00-089 |
Lars Engebretsen,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2000/089#revision1The 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.
Sun, 09 Sep 2001 00:00:00 +0300https://eccc.weizmann.ac.il/report/2000/089#revision1
Paper TR00-089
| Approximation Hardness of TSP with Bounded Metrics |
Lars Engebretsen,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2000/089The 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.
Sun, 03 Dec 2000 09:44:04 +0200https://eccc.weizmann.ac.il/report/2000/089