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.

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.