Dr. William J. Cook
University Professor, Combinatorics and Optimization
University of Waterloo
In Pursuit of the Salesman: Mathematics at the Limits of Computation
Thursday, April 6, 2017
5:45 p.m. Reception; 6:30 p.m. Lecture
Atrium, 2nd Floor, Richcraft Hall
The traveling salesman problem 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. 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 what computers can and cannot solve. In this talk, we discuss the history, applications, and computation of this fascinating problem.