IC Colloquim - Improving Christofides' Algorithm with Randomization and LP
Event details
| Date | 22.11.2013 |
| Hour | 15:15 › 16:30 |
| Speaker | David Shmoys - Cornell University |
| Location | |
| Category | Conferences - Seminars |
Abstract:
In 1976, Christofides gave an approximation algorithm for the traveling salesman problem (TSP) with metric costs that was guaranteed to find a tour that was no more than 3/2 times the length of the shortest tour visiting a given set of n cities; it remains an open problem to give a polynomial-time algorithm with a better performance guarantee.
We shall survey a number of recent results that have yielded improvements for significant special cases, and for related problems. Most importantly, there is now an algorithm conjectured to have a stronger guarantee. This algorithm emerged from a stream of work starting with a paper of Asadpour, Goemans, Madry, Oveis Gharan, and Saberi, and was proposed by Oveis Gharan, Saberi, and Singh. An, Kleinberg, and Shmoys show that a simpler variant, in the case of the s-t path TSP, improves upon Christofides¹ algorithm for general metric costs. Furthermore, Gao showed how to obtain a tight LP-based analysis for the s-t path TSP with costs derived as shortest paths in an underlying unweighted undirected graph.
Short bio:
David Shmoys obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held a faculty position at MIT before joining the Cornell faculty. He is the the director of the School of Operations Research and Information Engineering at Cornell, Co-Chair of the Academic Planning Committee for Cornell NYC Tech, and Associate Director of the Institute of Computational Sustainability at Cornell University. In addition, he is a Fellow of the ACM, INFORMS, and of SIAM, was an NSF Presidential Young Investigator.
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.
In 1976, Christofides gave an approximation algorithm for the traveling salesman problem (TSP) with metric costs that was guaranteed to find a tour that was no more than 3/2 times the length of the shortest tour visiting a given set of n cities; it remains an open problem to give a polynomial-time algorithm with a better performance guarantee.
We shall survey a number of recent results that have yielded improvements for significant special cases, and for related problems. Most importantly, there is now an algorithm conjectured to have a stronger guarantee. This algorithm emerged from a stream of work starting with a paper of Asadpour, Goemans, Madry, Oveis Gharan, and Saberi, and was proposed by Oveis Gharan, Saberi, and Singh. An, Kleinberg, and Shmoys show that a simpler variant, in the case of the s-t path TSP, improves upon Christofides¹ algorithm for general metric costs. Furthermore, Gao showed how to obtain a tight LP-based analysis for the s-t path TSP with costs derived as shortest paths in an underlying unweighted undirected graph.
Short bio:
David Shmoys obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held a faculty position at MIT before joining the Cornell faculty. He is the the director of the School of Operations Research and Information Engineering at Cornell, Co-Chair of the Academic Planning Committee for Cornell NYC Tech, and Associate Director of the Institute of Computational Sustainability at Cornell University. In addition, he is a Fellow of the ACM, INFORMS, and of SIAM, was an NSF Presidential Young Investigator.
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.
Links
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Ola Svensson