# 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

years later.

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.

*Biographical Sketch*

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.