Carl-Friedrich-Gauß-Vorlesung 2026
Prof. Dr. William J. Cook
The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours
Donnerstag, 07.05.2026, Aula, Haus der Wissenschaft, Pockelsstr. 11
In welcher Reihenfolge besucht man am besten eine Menge zu besuchender Orte? Das ist eines der bekanntesten schweren Optimierungsprobleme mit vielen praktischen Anwendungen. Der weltweit führende Experte Prof. Dr. William J. Cook wird im Rahmen der Gauß-Vorlesung beschreiben, wie man mit Witz und Verstand zielsicher die beste Rundreise bestimmen kann.
Die Veranstaltung ist offen für ein breites Publikum.
Abstract:
Amazon drivers hit the road every day, each taking a delivery van in a traveling
salesman problem (TSP) 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 in September 2025 reported "a laptop computer would
take 1,000 years to figure out the best course" for 22 cities. Claims such as
this ignore 70 years of intense study. A 22-city TSP can be handled easily 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 81,998 bars in Korea. 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.00016 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.