Dear Colleagues, let me to invite you to 123. Mathematical Colloquium - prof. William Cook (on this Thursday 6.4.2023)
https://kam.mff.cuni.cz/~klazar/cook.pdf ____________________________________________________________________
123. kolokvium:
THE TRAVELING SALESMAN PROBLEM
W. Cook
ctvrtek 6. dubna 2023 ve 14:00, aula (refektar), prvni patro
MFF UK, Malostranske nam. 25, Praha 1 ____________________________________________________________________
Abstract. Is it possible to compute the shortest route through a large number of stops? The task, known as the traveling salesman problem, or TSP for short, sounds simple enough. And it arises in many practical contexts, such as guiding a van to bring packages to your doorstep.
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. Going larger, we describe techniques that have been used to find to precise optimality the shortest walk to 49,687 pubs in the UK. Or if you need to visit the nearest 2,079,471 stars, there is a route, ready to go, that is guaranteed to be no more than 1.0000074 times longer than 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.
We will discuss the history of the TSP and its applications, together with computational efforts towards exact and approximate solutions.