The traveling salesman problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem an algorithm that for any fixed epsilon > 0 computes in randomized polynomial time a (1 + epsilon)-approximation to the optimal tour in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [J. ACM, 45 (1998), pp. 753-782] and Mitchell [SIAM J. Comput., 28 (1999), pp. 1298-1309] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar.
展开▼
机译：旅行商问题（TSP）是最著名的NP困难优化问题。我们针对该问题设计了一种算法，该算法对于任何大于0的固定epsilon，都会在随机多项式时间内计算出（1 + epsilon）逼近TSP实例中的最优行程，从而形成具有有限内在维数的任意度量空间。 Arora的著名成果[J. ACM，45（1998），pp.753-782]和Mitchell [SIAM J. Comput。，28（1999），pp.1298-1309]证明上述结果在固定维数的TSP的特殊情况下成立。欧氏空间。因此，我们的算法证明了度量TSP的算法易处理性取决于空间的维数，而不取决于其特定的几何形状。该结果解决了自Talwar的拟多项式时间算法以来一直存在的问题。
展开▼
