The Return of the Traveling Salesman: Approximation Algorithm Design via Randomization and Linear Programming
Dr. David B. Shmoys
Cornell University
Thursday, October 30, 2014
11:00 a.m., 1000 SEO Building
Abstract: Heading link
The traveling salesman problem (TSP) has stimulated work in a number of areas, ranging from computational complexity to algorithm engineering; in this problem, we are given a set of n cities along with the distance between each pair, which we assume are symmetric and satisfy the triangle inequality, and we wish to find the minimum-length tour that visits each city once. In spite of a vast improvement over the past 40 years in our ability to derive both positive and negative results for approximation algorithms ? polynomial-time algorithms with a provable relative error performance guarantee ? there has been only minimal progress for the TSP; we know that a polynomial-time algorithm guaranteed to yield better than 123/122 times the optimum would imply that P=NP, and the best known approximation algorithm is Christofides Algorithm from the mid-1970s, which finds a solution of cost at most 3/2 times the optimum. Although randomization and linear programming have become indispensable tools in the algorithm designers toolkit, recent work has shown that both can be exploited more extensively to obtain improved algorithms. We will discuss a number of these developments, focusing on results on variants of the TSP, starting with work of Asadpour, Goemans, Madry, Oveis Gharan, & Saberi and of Oveis Gharan, Saberi, & Singh that has now led to improvements to Christofides Algorithm, not for the ordinary TSP, but for the s-t path TSP, in which we are also given two specified endpoints s and t, and the aim is to find the minimum-length path between s and t, visiting each other city once along the way.
This is joint work with Hyung-Chun An and Bobby Kleinberg.
Bio: Heading link
David Shmoys is the Laibe/Acheson Professor and Director of the School of Operations Research and Information Engineering at Cornell University. He obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell faculty. He is also Associate Director of the Institute of Computational Sustainability at Cornell University. He is a Fellow of the ACM, INFORMS, and of SIAM, was an NSF Presidential Young Investigator, and has served on numerous editorial boards, including Mathematics of Operations Research (for which he is currently an Associate Editor), and the SIAM Journals of both Computing and Discrete Mathematics, where for the latter he also served as Editor-in-Chief. He has been the advisor for 21 graduated PhD students, and his former students are currently on the faculties of many leading universities and research labs, including MIT, Waterloo, Brown, Maryland, Georgetown, and D-Wave. Shmoys’ research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, and most recently, computational sustainability. His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems; his recent book, co-authored with David Williamson, The Design of Approximation Algorithms, was awarded the 2013 Lanchester Prize by INFORMS.
Host: Bhaskar DasGupta