The Traveling Salesman Problem: Amazon Deliveries, Pub Walks, and Astro ToursPublic Event
by
Zusammenfassung:
Is it possible to compute the shortest route through a large number of stops? The task, known as the traveling salesman problem, strikes fear in the heart of the computing world. The Washington Post reports it would take "1,000 years to compute the most efficient route between 22 cities." Claims such as this, however, ignore 70 years of intense study. A 22-city TSP can be handled easily with modern methods. Indeed, we discuss techniques used to find to precise optimality the shortest walking tour to 81,998 pubs in Korea and to find approximate solutions to visit over 100,000,000 stars.
The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques. 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.
Dies Academicus