기초과학연구원 이산수학그룹
On October 22, 2025, William Cook from the University of Waterloo gave a public lecture on the traveling salesman problem at the ST Center, Seoul during the 2025 KMS Annual Meeting. The title of his talk was “The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours.” This public lecture was co-organized by the IBS Discrete Mathematics Group.
On October 21, 2025, William Cook from University of Waterloo gave a talk at the Discrete Math Seminar on using branch-decompositions for discrete optimization problems, including the traveling salesman problem. The title of his talk was “Optimization via Branch Decomposition“.
We are pleased to share an exciting public lecture as part of the 2025 Annual Meeting of the Korean Mathematical Society (KMS), featuring one of the world’s leading researchers in combinatorial optimization. This event is sponsored by the IBS Discrete Mathematics Group.
👤 Speaker: William Cook
🏛 Affiliation: Department of Combinatorics and Optimization, University of Waterloo
📅 Date: October 22, 2025 (Wednesday), 7:00 PM
📍 Venue: ST Center, Seoul (near Gangnam Station)
한국과학기술회관 B1, 과학기술컨벤션센터, 대회의실 2 (강남역 인근)
🗣 Language: English
🎟 Admission: Free of charge
The Traveling Salesman Problem (TSP) asks a deceptively simple question:
What is the shortest possible route that visits a set of locations exactly once and returns to the starting point?
Despite its simplicity, the TSP is a cornerstone of combinatorial optimization and theoretical computer science, long considered difficult due to its computational complexity.
In this public lecture, William Cook, a leading authority on the TSP, will discuss:
The TSP remains a central example in complexity theory, showing how sustained mathematical effort can solve problems once deemed impossible.
William Cook is a professor emeritus at the University of Waterloo and an internationally recognized expert on combinatorial optimization.
He is the author of the acclaimed book In Pursuit of the Traveling Salesman and has contributed extensively to both the theory and computation of hard optimization problems.
Whether you’re a student interested in algorithms, a researcher in discrete mathematics, or simply curious about how math solves real-world problems — this is a lecture not to be missed.
📍 Location: ST Center, Seoul
🕖 Time: 7:00 PM, Wednesday, October 22, 2025
🎟 Admission: Free | 🗣 Language: English
🔗 More info about KMS 2025 Annual Meeting
📧 For inquiries: contact@kms.or.kr
Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We will discuss the computational issues involved in using branch-width as as a general tool in discrete optimization.
On March 6, 2024, William Cook from the University of Waterloo gave a colloquium talk on the Traveling Salesman Problem. The title of his talk was “The Traveling Salesman Problem: Amazon Deliveries, Pub Walks, and Astro Tours“.
Amazon drivers hit the road every day, each taking a Prime van in a traveling salesman problem tour through 150 or more customer stops. But even a whisper of the TSP strikes fear in the heart of the computing world. A Washington Post article reported it would take “1,000 years to compute the most efficient route between 22 cities.” Claims such as this, however, ignore 70 years of intense study. A 22-city TSP can be handled in a snap with modern methods, even on an iPhone. And, coming to the aid of Amazon drivers, we describe techniques used to win the $100,000 top prize in the Amazon Last Mile Routing Challenge, together with Stephan Held and Keld Helsgaun.
Going larger, we discuss methods used to find to precise optimality the shortest walking tour to 49,687 pubs in the UK. Even larger, if you want to visit 136,606,128 stars, there is a 3D route, ready to go, that is guaranteed to be no more than 1.00018 times longer that a shortest-possible tour.
The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this discussion, demonstrating whether or not focused efforts on a single, possibly unsolvable, model will produce results beyond our expectations.