__
Revision #1 to TR96-046 | 14th November 1996 00:00
__
#### When Euclid Meets Hamming: the Approximability of Geometric TSP and MST Revision of: TR96-046

**Abstract:**
We prove that the Traveling Salesperson Problem (TSP),

the Minimum Steiner Tree Problem (MST), the Minimum

k-Steiner Tree problem (MkST) and the k-Center Problem

are MAXSNP-hard (and thus NP-hard to approximate within

some constant <i>r</i> > 1) even if all cities (respectively,

points) lie in the geometric space $R^n$ (<i>n</i> is

the number of cities/points) and distances are computed

with respect to the $l_1$ (rectilinear) metric.

The TSP and k-Center hardness results also hold for any $l_p$

metric, including the <i>Euclidean</i> $\ell_2$ metric, and

(under randomized reductions) also in $\rea^{\log n}$ for the

Euclidean metric.

Arora's approximation scheme for Euclidean TSP in $\rea^d$ runs

in time $n^{\tilde O(\log^{d-2} n)/\epsilon^{d-1}}$ and

achieves approximation $(1+\epsilon)$; our result implies

that this running time cannot be improved to $n^{d/\epsilon}$

unless NP has subexponential randomized algorithms. We also prove,

as an intermediate step, the hardness of approximating the above

problems in <i>Hamming spaces</i>. The only previous hardness

results involved metrics where all distances are 1 or 2.

__
TR96-046 | 27th August 1996 00:00
__

#### On the Approximability of the Multi-dimensional Euclidean TSP

**Abstract:**
We consider the Traveling Salesperson Problem (TSP) restricted

to Euclidean spaces of dimension at most k(n), where n is the number of

cities. We are interested in the relation between the asymptotic growth of

k(n) and the approximability of the problem. We show that the problem is

Max SNP-hard when k(n) = n-1. Thus, for a certain constant e1>0, the

(n-1)-dimensional Euclidean TSP cannot be approximated within a factor

(1+e1) in polynomial time, unless P=NP. Using a previous result about

embedding of Euclidean metrics in low-dimensional spaces, we can also prove

that constants c and e2 exist such that approximating the

(c log n)-dimensional Euclidean TSP within 1+e2 is NP-hard under randomized

reductions (and thus not solvable in P, unless RP=NP). This contrasts with

a recent result by Arora who presented a polynomial time approximation

scheme for the bidimensional Euclidean TSP. Additionally, we note

extensions of our result to other geometric metrics.