The shortest traveling salesman route going through all 13,509 cities in the United States with a population of at least 500 (as of 1998).
Not long ago, a team of researchers from Stanford and McGill universities broke a 35-year record in computer science by an almost imperceptible margin — four hundredths of a trillionth of a trillionth of a trillionth of a trillionth of a percent, to be exact.
...
In 1976, Nicos Christofides, a professor at Imperial College London, developed an algorithmthat produces routes guaranteed to be at most 50 percent longer than the shortest route.
...
Finally in 2011, the Stanford-McGill team edged past Christofides’ 50 percent guarantee for certain types of traveling salesman problems, showing that its algorithm’s solutions would be at most 49.99999999999999999999999999999999999999999999999996 percent longer than the true answer.
http://www.wired.com/wiredscience/2013/01/traveling-salesman-problem/al…