Traveling Salesperson Algorithm Improved

Classic problem often used as a benchmark for algorithmic solutions.

Computer Scientists Break the 'Traveling Salesperson' Record From Quanta Mag

Finally, there’s a better way to find approximate solutions to the notorious optimization problem, often used to test the limits of efficient computation.

WHEN NATHAN KLEIN started graduate school two years ago, his advisers proposed a modest plan: to work together on one of the most famous, long-standing problems in theoretical computer science.

Even if they didn’t manage to solve it, they figured, Klein would learn a lot in the process. He went along with the idea. “I didn’t know to be intimidated,” he said. “I was just a first-year grad student—I don’t know what’s going on.”

Now, in a paper posted online in July, Klein and his advisers at the University of Washington, Anna Karlin and Shayan Oveis Gharan, have finally achieved a goal computer scientists have pursued for nearly half a century: a better way to find approximate solutions to the traveling salesperson problem.

This optimization problem, which seeks the shortest (or least expensive) round trip through a collection of cities, has applications ranging from DNA sequencing to ride-sharing logistics. Over the decades, it has inspired many of the most fundamental advances in computer science, helping to illuminate the power of techniques such as linear programming. But researchers have yet to fully explore its possibilities—and not for want of trying.

The traveling salesperson problem “isn’t a problem, it’s an addiction,” as Christos Papadimitriou, a leading expert in computational complexity, is fond of saying.

Most computer scientists believe that there is no algorithm that can efficiently find the best solutions for all possible combinations of cities. But in 1976, Nicos Christofides came up with an algorithm that efficiently finds approximate solutions—round trips that are at most 50 percent longer than the best round trip. At the time, computer scientists expected that someone would soon improve on Christofides’ simple algorithm and come closer to the true solution. But the anticipated progress did not arrive.

“A lot of people spent countless hours trying to improve this result,” said Amin Saberi of Stanford University.

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.  .... "