Abstract:

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).

Short Bio:
Lee-Ad Gottlieb is a postdoc fellow at Hebrew University. He completed his 
Ph.D. at NYU's Courant Institute, advised by Richard Cole. Lee-Ad's 
research focuses primarily on proximity problems in metric space, with 
emphasis on machine learning, computational geometry and metric 
embeddings.