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.
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.
Meet our speaker and chair
William Cook (@wjcook) is a Professor at the University of Waterloo and specialises in Combinatorics and Optimization. He is the founding editor-in-chief of the journal Mathematical Programming Computation, and the former editor-in-chief of Mathematical Programming (Series B and Series A).
László Végh is a professor in the Operations Research Group in the Mathematics Department at LSE. He joined the School in 2012, and teaches and researches topics in algorithms and optimisation.
More about this event
This event will be available to watch on LSE Live. LSE Live is the new home for our live streams, allowing you to tune in and join the global debate at LSE, wherever you are in the world. If you can't attend live, a video will be made available shortly afterwards on LSE's YouTube channel.
The Department of Mathematics (@LSEMaths), located within a world-class social science institution, aims to be a leading centre for mathematics in the social sciences. We have a stimulating and active research environment and offer a wide range of degree programmes and courses.
Twitter Hashtag for this event: #LSEBillCook
Podcast & Video
A podcast of this event is available to download from The Travelling Salesman Problem
A video of this event is available to watch at The Travelling Salesman Problem
Podcasts and videos of many LSE events can be found at the LSE Public Lectures and Events: podcasts and videos channel.