Bill Cook, Johns Hopkins University

Abstract

Given a collection of points, the TSP asks for the shortest route to visit them all. Simple enough. But even a whisper of the problem strikes fear in the heart of the computing world. Last year, a Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities." This claim, however, ignores 70 years of intense study. A 22-city TSP can be handled in a snap with modern algorithms, even on an iPhone. Going larger, we describe techniques that have been used to solve to precise optimality examples with nearly 50,000 points and Google Map walking distances. And if you need to visit the nearest 2,079,471 stars, there is a route, ready to go, that is guaranteed to be no more than 1.000009 times longer than a shortest possible tour.

This work follows a long line of computational research going back to Julia Robinson in 1949 and Dantzig, Fulkerson, and Johnson in 1954. We will discuss the history of the TSP and its applications, together with recent computational efforts towards exact and approximate solution methods. The talk is based on joint work the David Applegate, Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.

Speaker Bio: Bill Cook is Professor of Applied Mathematics and Statistics at Johns Hopkins University. His research interests lie in integer programming and combinatorial optimization, where he is especially known for his work on the Traveling Salesman Problem (TSP). Cook is a member of the National Academy of Engineering and a Fellow of the AMS, INFORMS, and SIAM. He is a recipient of the Beale-Orchard-Hays Prize of Mathematical Programming Society and the Lanchester Prize for his book (with Applegate, Bixby, and Chvatál) The Traveling Salesman Problem: A Computational Study. In 1998, he was an invited speaker at the International Congress of Mathematicians. Cook was an organizer of the DIMACS Special Year on Combinatorial Optimization and has taken part in DIMACS Implementation Challenges, both as an organizer (of the 2nd Challenge on NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability) and a competitor (in the 8th Challenge on the Traveling Salesman Problem).

Video