The Goldman Distinguished Lecture Series: William Cook (University of Waterloo) @ Shaffer 100
Title: Information, Computation, Optimization: Connecting the dots in the Traveling Salesman Problem
Abstract: Few math models scream impossible as loudly as the traveling salesman problem.
Given n cities, the TSP asks for the shortest route to take you to all of them.
Easy to state, but if P ≠ NP then no solution method can have good asymptotic
performance as n goes off to infinity. The popular interpretation is that we simply
cannot solve realistic examples. But this skips over nearly 70 years of intense
mathematical study. Indeed, in 1949 Julia Robinson described the TSP challenge in
practical terms: “Since there are only a finite number of paths to consider, the
problem consists in finding a method for picking out the optimal path when n is
moderately large, say n = 50.” She went on to propose a linear programming attack
that was adopted by her RAND colleagues Dantzig, Fulkerson, and Johnson several
Following in the footsteps of these giants, we show that a certain tour of 49,603
historic sites in the US is shortest possible, measuring distance with point-to-point
walking routes obtained from Google Maps. Along the way, we discuss the history,
applications, and computation of this fascinating problem.
William Cook is a University Professor in Combinatorics and Optimization at the University of Waterloo, where he received his Ph.D. in 1983. Bill
was elected a SIAM Fellow in 2009, an INFORMS Fellow in 2010, a member of the National Academy of Engineering in 2011, and an American
Mathematics Society Fellow in 2012. He is the author of the popular book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.
Bill is a former Editor-in-Chief of the journals Mathematical Programming (Series A and B) and Mathematical Programming Computation. He is the past chair and current vice-chair of the Mathematical Optimization Society and a past chair of the INFORMS Computing Society.