Luca Trevisan.
When Hamming Meets Euclid: the Approximability of
Geometric TSP and MST.
To appear in the Proceedings
of the 29th Symposium
on Theory of Computing.
ACM, 1997.
 Abstract

We prove that the Traveling Salesperson Problem (TSP) and
the Minimum Steiner Tree Problem (MST) are MAX SNPhard (and thus
NPhard to approximate within some constant $r>1$) even if all cities
(respectively, points) lie in the geometric space $R^n$ ($n$ is the
number of cities/points) and distances are computed with respect to
the $l_1$ (rectilinear) metric.
The TSP hardness results also hold for any $l_p$ metric, including
the Euclidean metric, and in $R^{log n}$.
The running time of Arora's approximation scheme for geometric TSP
in $R^d$ is doubly exponential in $d$. Our results imply that this
dependance is necessary unless NP has subexponential algorithms.
We also prove, as an intermediate step, the hardness of approximating
TSP and MST in Hamming spaces. The reduction for TSP uses errorcorrecting
codes and random sampling; the reduction for MST uses the integrality
property of MINCUT. The only previous nonapproximability results for
TSP and MST involved metrics where all distances are 1 or 2.