Marginal Improvement is a Big Victory in Solving the Travelling Salesman Problem

Image: David Applegate, Robert Bixby, Vasek Chvatal and William Cook

In 1930, Harvard mathematician Karl Menger (he of the Menger Sponge fame) asked a simple question: what is the shortest route a salesman has to take, in order to visit every city (of a certain size) in the United States and return to his starting place? That should be easy enough, right? After all, you only have to check every possible round trip routes to find the shortest one.

Turned out, brute force doesn't work well in solving the Travelling Salesman Problem, even with the fastest computer. With 10 cities, you'd have to check about 300,000 different round trip routes. Add just 5 more cities to that mix, and you'd have to check more than 87 billion.

In 1972, computer scientists Richard Karp of UC Berkeley wrote a seminal paper, claiming that the Travelling Salesman Problem may not even be solvable. Undaunted, countless mathematicians and computer scientists spent years of their lives trying to prove that wrong, but the best algorithm they could come up with only found approximate solutions. In 1976, Nicos Christofides developed an algo that found a route guaranteed to be, at worst, 50% longer than the shortest route. That was a great victory and everyone thought that it was only a matter of months before someone refined it and found the correct solution.

Decades later, Christofides algorithm still stood. Until 2011, when a team of mathematicians from Stanford and McGill universities came up with an algorithm that is marginally better. 0.0000000000000000000000000000000000000000000000000004% better, in fact. And what a victory that was because it showed a crack in the Travelling Salesman Problem that has haunted mathematicians for decades.

Read more about the hunt for the solution for the Travelling Salesman Problem in this neat article by Erica Klarreich/Simon Science News over at Wired: Link (no math required, promise!)