Information, Computation, Optimization - Connecting the Dots in the Traveling Salesman Problem

Explore the fascinating world of optimization and its applications in this 51-minute MAA Invited Address given by William Cook from the University of Waterloo at the 2018 Joint Mathematics Meetings. Delve into the connections between information, computation, and optimization through the lens of the Traveling Salesman Problem. Learn about linear programming, polyhedral approaches, and cost refinement techniques. Discover how these concepts apply to real-world scenarios, including the US problem, the McNally Atlas, and intriguing examples involving pubs, air dishes, and even extraterrestrial considerations. Gain insights into the Gaia project and its implications for optimization. Conclude with a thought-provoking Q&A session that further expands on the presented concepts.

Introduction
Optimization
Linear Programming
Polyhedral Approach
Traveling Salesman Problem
US Problem
McNally Atlas
Cost Refinement
Pubs
Air Dish Alien
Gaia
The Alien
Conclusion
Questions