Large 00004

Algorithmic Frontiers of Doubling Metric Spaces

Robert Krauthgamer

Recorded 14 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


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 and of Mitchell 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.

Joint work with Yair Bartal and Lee-Ad Gottlieb.

Watched 1011 times.