When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

Abstract

We prove that the traveling salesman problem ({\sc Min TSP}) is {\sf Max SNP}-hard (and thus {\sf NP}-hard to approximate within some constant r1) even if all cities lie in a Euclidean space of dimension $\log n$ ($n$ is the number of cities) and distances are computed with respect to any lp norm. The running time of recent approximation schemes for geometric {\sc Min TSP} is doubly exponential in the number of dimensions. Our result implies that this dependence is necessary unless NP has subexponential algorithms. As an intermediate step, we also prove the hardness of approximating {\sc Min TSP} in Hamming spaces. Finally, we prove a similar, but weaker, inapproximability result for the Steiner minimal tree problem ({\sc Min ST}). The reduction for {\sc Min TSP} uses error-correcting codes; the reduction for {\sc Min ST} uses the integrality property of {\sc Min-Cut} linear programming relaxations. The only previous inapproximability results for metric {\sc Min TSP} involved metrics where all distances are 1 or 2.