Wednesday, December 16, 12:00 noon
Frist Multipurpose Room B
In Pursuit of the Salesman: Mathematics at the Limits of Computation
Bill Cook
The traveling salesman problem, or TSP for short, is easy to state: given a number of cities along with the cost of travel between each pair of them, find the cheapest way to visit them all and return to your starting point. Easy to state, but difficult to solve! Despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute-force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem. This is a deep mathematical question: Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stout-hearted who would like to tackle the general version of the TSP, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient general method or prove an impossibility result.
The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. This is not to say that mathematicians have thus far come away empty-handed. Within the theoretical community the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, when the optimal tour was pulled out of a mind-boggling number of candidates in a computation that took the equivalent of 136 years on top-of-the-line computer workstations. On the practical side, solution methods are used to compute optimal or near-optimal tours for a host of applied problems on a daily basis, from genome sequencing to arranging music on iPods.
In this talk we discuss the history, applications, and computation of this fascinating problem.
Speaker Bio: Bill Cook is the Chandler Family Chair in the School of Industrial and Systems Engineering at Georgia Tech. He received his Ph.D. in Combinatorics and Optimization from the University of Waterloo in 1983. Cook spent two years as an Alexander von Humboldt Research Fellow at the University of Bonn, and he has held positions at Cornell, Columbia, Bellcore, Rice, and Princeton. He is a former Editor-in-Chief of Mathematical Programming (1999--2007) and he is currently the Editor-in-Chief and Founding Editor of the new journal Mathematical Programming Computation. Cook is also a member of the Editorial Boards of Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, and SIAM Journal on Optimization. Together with David Applegate, Robert Bixby, and Vasek Chvatal, he was awarded the 2000 Beale-Orchard-Hayes Prize by the Mathematical Programming Society and in 2007 their book The Traveling Salesman Problem: A Computational Study (Princeton University Press) was awarded the Lanchester Prize by INFORMS; at an earlier stage, their TSP work was named one of the Top 50 Science Stories of 1992 by Discover Magazine. Cook was named the 2003 I. E. Block Community Lecturer by the Society for Industrial and Applied Mathematics (SIAM) and he was named a SIAM Fellow in 2009.
