The Travelling Salesman Problem | LSE Event

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.
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.
Speaker:
Professor William Cook
Chair:
Professor Jan van den Heuvel
Full details/attend: www.lse.ac.uk/...
To turn on captions, go to the bottom-right of the video player and click the icon. Please note that this feature uses Automatic Speech Recognition (ASR) technology, or machine generated transcription, and is not 100% accurate.