The Travelling Salesman Problem
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.
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.
Wednesday 3 May 2023 | 1 hour 23 minutes 6 seconds
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 discuss the history of the TSP and its applications, together with computational efforts towards exact and approximate solutions.