Event

Fields-Carleton Distinguished Lecture Series 2017

Friday, April 7, 2017
6:30 PM - 8:00 PM
Atrium (Second Floor) Richcraft Building
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
Register here

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.