Technion
 
         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-   <http://www.cs.technion.ac.il/~colloq>
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>