The Travelling Salesman Problem
LSE: Public lectures and events
English - May 03, 2023 00:00 - 1 hour - 66.6 MB - ★★★★ - 256 ratingsCourses Education Homepage Download Apple Podcasts Google Podcasts Overcast Castro Pocket Casts RSS feed
Previous Episode: The Dialogical Roots of Deduction
Next Episode: Shaping a 21st Century Policy Consensus
Contributor(s): Professor William Cook | 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.