Fields-Carleton Distinguished Lecture
The Fields-Carleton Distinguished Lecture is annual lecture sponsored by the Fields Institute and Carleton University featuring international-renowned speakers with expertise in mathematics, statistics and theoretical computer science. Recent guest speakers include Uffe Haagerup (University of Copenhagen); Thomas C. Hales (University of Pittsburgh); Kenneth R. Davidson (University of Waterloo); Donald Dawson (Carleton University); V. Kumar Murty (University of Toronto); Philippe Flajolet (INRIA); Jerrold Marsden (California Institute of Technology); and, Donald Saari (University of California, Irvine).
Each guest speaker delivers a public lecture as well as a Research Lecture, which is more technical in nature.
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.
About the speaker
William Cook is 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.
The traveling salesman problem with road distances
Friday, April 7, 2017
MacPhail Room, 4351 Herzberg Laboratories
Following Dantzig, Fulkerson, and Johnson, we show that a certain tour of 49,603 sites in the US is the shortest possible, measuring distance with point-to-point routes obtained from Google Maps. We highlight aspects of algorithms, combinatorics, and optimization that make the computation possible, including a cost-refinement technique to generate lower bounds on the tour length. The talk is based on joint work with Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.