Close

Events

The Travelling Salesman Problem

Hosted by the Department of Mathematics

In-person and online public event (Auditorium, Centre Building)

Speaker

Professor William Cook

Professor William Cook

Chair

Professor Laszlo Vegh

Professor Laszlo Vegh

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.

LSE Blogs
Many speakers at LSE events also write for LSE Blogs, which present research and critical commentary accessibly for a public audience. Follow British Politics and Policy, the Business Review, the Impact Blog, European Politics and Policy and the LSE Review of Books to learn more about the debates our events series present.

Live captions

Automated live captions are available at this live event. Please note that this feature uses Automatic Speech Recognition (ASR) technology, or machine generated transcription and is not 100% accurate.

Photography

Photographs taken on behalf of LSE are often used on our social media accounts, website and publications. At events, photographs could include broad shots of the audience and lecture theatre, of speakers during the talk, and of audience members as they participate in the Q&A.

If you are photographed participating in an event Q&A but would not like your photograph to be stored for future use, please contact events@lse.ac.uk.

Podcasts
We aim to make all LSE events available as a podcast subject to receiving permission from the speaker/s to do this, and subject to no technical problems with the recording of the event. Podcasts are normally available 1 week after the event. Podcasts and videos of past events can be found online.

Social Media

Follow LSE public events on Twitter for notification on the availability of an event podcast, the posting of transcripts and videos, the announcement of new events and other important event updates. Event updates and other information about what’s happening at LSE can be found on the LSE's Facebook page and for live photos from events and around campus, follow us on Instagram. For live webcasts and archive video of lectures, follow us on YouTube. 

LSE in Pictures is a selection of images taken by the school photographer.

Accessibility
If you are planning to attend this event and would like details on how to get here and what time to arrive, as well as on accessibility and special requirements, please refer to LSE Events FAQ.  LSE aims to ensure that people have equal access to these public events, but please contact the events organiser as far as possible in advance if you have any access requirements so that arrangements, where possible, can be made. If the event is ticketed, please ensure you get in touch in advance of the ticket release date. Access Guides to all our venues can be viewed online.

WIFI Access
LSE has now introduced wireless for guests and visitors in association with 'The Cloud', also in use at many other locations across the UK. If you are on campus visiting for the day or attending a conference or event, you can connect your device to wireless. See more information and create an account at Join the Cloud.
Visitors from other participating institutions are encouraged to use eduroam. If you are having trouble connecting to eduroam, please contact your home institution for assistance.
The Cloud is only intended for guest and visitor access to wifi. Existing LSE staff and students are encouraged to use eduroam instead.
From time to time there are changes to event details so we strongly recommend that if you plan to attend this event you check back on this listing on the day of the event.

Share

This event will be streamed live on YouTube.

  Sign up for news about events