ACM News 01/02/2013
Researchers from Stanford and McGill Universities in 2011 discovered a way to improve upon a 35-year-old algorithm that, up until then, was the best solution to the vexing traveling salesman problem, and that breakthrough inspired other researchers to reexamine the problem and devise significantly better algorithms. The traveling salesman problem asks for the shortest route that visits every city in a group of cities linked by highways, then returns to the original city. Although it would appear the problem could easily be solved by checking each round-trip route to determine which is shortest, as more cities are added to the group, the number of round-trips quickly outpaces the ability of even the fastest computers to calculate the answer, reaching over 87 billion possible routes with just 15 cities. In 1976, professor Nicos Christofides developed an algorithm that finds a route no more than 50 percent longer than the shortest route, and that stood as the best solution until the Stanford-McGill team found a way to beat Christofides’ algorithm. Following the Stanford-McGill team’s breakthrough, other teams used rounding methods to produce even better algorithms, with the current record able to find a route no more than 40 percent longer than the shortest.
More info: Wired News (01/30/13) Erica Klarreich