• Calendar

February 7, Tuesday
12:00 – 13:00

The doubling dimension is a natural measure of the richness of a metric space. It was first considered by Assouad in the context of metric embeddings, and has since found its way into the algorithms and machine learning communities. Ultimately, the doubling dimension provides a way to generalized many results tailored for low-dimensional Euclidean space to apply to more general metric space. The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+eps)-approximation to the optimal tour, for any fixed eps>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora (A-98) and Mitchell (M-99) 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 (T-04).