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. Read from source….