Computer Scientists Break the 'Traveling Salesperson' Record

Most computer scientists believe that there is no algorithm that can efficiently find the best solutions for all possible combinations of cities.

Now Karlin, Klein and Oveis Gharan have proved that an algorithm devised a decade ago beats Christofides’ 50 percent factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that it will open the floodgates to further improvements.