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

摘要: We prove that the traveling salesman problem ({\sc Min TSP}) is {\sf 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$ number cities) and distances are computed with respect any lp norm. The running time recent approximation schemes for geometric {\sc TSP} doubly exponential dimensions. Our result implies this dependence necessary unless NP has subexponential algorithms. As an intermediate step, we also hardness approximating Hamming spaces. Finally, similar, but weaker, inapproximability Steiner minimal tree ST}). reduction uses error-correcting codes; ST} integrality property Min-Cut} linear programming relaxations. only previous results metric involved metrics where 1 or 2.