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.
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.