Computer Science Colloquium
Time+Place : Sunday 25/12/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Lee-Ad Gottlieb
Affiliation: Hebrew University
Host       : Nir Ailon
Title      : The traveling salesman problem: Low-dimensionality implies
             a polynomial time approximation scheme.
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.
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>