When Nathan Klein started graduate school two years ago, his advisors proposed a modest plan: to work together on one of the most famous and long-standing problems in theoretical computer science.
Even if they couldn’t solve it, they thought, Klein would learn a lot in the process. He accepted the idea. “I didn̵
Now, in a paper published online in July, Klein and his University of Washington advisors Anna Karlin and Shayan Oveis Gharan have finally achieved a goal that computer scientists have been pursuing for nearly half a century: a better way to find rough solutions to the peddler 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 computing, helping to illuminate the power of techniques such as linear programming. But researchers have yet to fully explore its possibilities, and not for lack of trying.
The peddler problem “is not a problem, it’s an addiction”, as Christos Papadimitriou, one of the leading experts in computational complexity, likes to say.
Most computer scientists believe that no algorithm exists that can efficiently find the best solutions for all possible city combinations. But in 1976, Nicos Christofides invented an algorithm that efficiently finds approximate solutions: round trips that are at most 50% longer than the best round trip. At the time, computer scientists expected that someone would soon improve Christofides’ simple algorithm and come close to the real solution. But the anticipated progress has not arrived.
“Many people have spent countless hours trying to improve on this result,” said Amin Saberi of Stanford University.
Now Karlin, Klein and Oveis Gharan have shown that an algorithm devised ten years ago beats Christofides’ factor of 50 percent, although they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this tiny improvement breaks both a theoretical and a psychological obstacle. The researchers hope it will open the door for further improvements.
“This is an achievement that I have wanted my entire career,” said David Williamson of Cornell University, who has been studying the problem of street vendors since the 1980s.
The peddler problem is one of the few fundamental problems that theoretical computer scientists repeatedly turn to to test the limits of efficient computing. The new result “is the first step towards proving that the frontiers of efficient computing are actually better than we thought,” Williamson said.
While there is probably no efficient method that always finds the shortest journey, it is possible to find something almost as good: the shortest tree that connects all cities – a network of connections (or “edges”) with no closed circuits . Christofides’ algorithm uses this tree as the backbone for a round trip tour, adding extra borders to convert it into a round trip.
Any round trip route must have an even number of borders in each city, as each arrival is followed by a departure. It turns out that the reverse is also true: if every city in a network has an even number of connections, the edges of the network must trace a round trip.
The shorter tree that connects all cities lacks this uniformity property, as each city at the end of a branch has only one connection with another city. So, to turn the shorter tree into a round trip, Christofides (who died last year) found the best way to connect pairs of cities that have an odd number of edges. So it proved that the resulting round trip will never be more than 50% longer than the best possible round trip.
In doing so, he devised perhaps the most famous approximation algorithm in theoretical computer science, one that usually forms the prime example in textbooks and courses.
“Everyone knows the simple algorithm,” said Alantha Newman of the University of Grenoble Alpes and the National Center for Scientific Research in France. And when you know, he said, “you know the state of the art”, or at least you did until last July.