When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree
We prove that the traveling salesman problem (MIN TSP) is Max SNP-hard (and thus NP-hard to approximate within some constant r > 1) 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 l(p) norm. The running time of recent approximation schemes for geometric 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 prov the hardness of approximating MIN TSP in Hamming spaces. Finally, we prove a similar, but weaker, inapproximability result for the Steiner minimal tree problem (MIN ST). The reduction for Min TSP uses error-correcting codes; the reduction for MIN ST uses the integrality property of MIN-CUT linear programming relaxations. The only previous inapproximability results for metric MIN TSP involved metrics where all distances are 1 or 2.
traveling salesman problem hardness of approximation computational complexity combinatorial optimization steiner tree problem