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

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

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.