Luca Trevisan.<br>
<b>When Hamming Meets Euclid: the Approximability of
Geometric TSP and MST.</b><br>
To appear in the <i><a href="http://sigact.acm.org/stoc97/">Proceedings 
of the 29th Symposium
on Theory of Computing.</i></a><br>
ACM, 1997.

<dl>

<dt> <b> Abstract</b> <dd>
We prove that the Traveling Salesperson Problem (TSP) and
the Minimum Steiner Tree Problem (MST) are MAX SNP-hard (and thus 
NP-hard 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 sub-exponential algorithms.

We also prove, as an intermediate step, the hardness of approximating 
TSP and MST in Hamming spaces. The reduction for TSP uses error-correcting
codes and random sampling; the reduction for MST uses the integrality 
property of MIN-CUT. The only previous non-approximability results for 
TSP and MST involved metrics where all distances are 1 or 2.
</dl>