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>