When Nathan Klein started graduate school two years ago, his advisers proposed a modest plan: to work together on one of the most popular, long-standing computer theoretical problems.
Although they did not solve it, they thought, Klein would learn a lot in the process. He followed the idea. “I didn̵7;t know I was intimidated,” he said. “I was a first-year student just graduating – I had no idea what was going on.”
Now, in a paper posted online in July, Klein and his University of Washington advisers Anna Karlin and Shayan Oveis Gharan have finally achieved a goal that computer scientists have pursued almost half a century traveling salesperson problem.
This optimization problem, which seeks the shortest (or most expensive) rotation through a collection of cities, has applications ranging from DNA sequencing to logistics sharing. Over the decades, it has inspired many of the most important advances in computer science, helping to explain the power of techniques such as linear programs. But researchers have not yet fully discovered its possibilities — and not for want of testing.
The problem with selling “is not a problem, it is an addiction,” as Christos Papadimitriou, a leading expert on computational complexity, is adamant.
Most computer scientists believe that no algorithm can efficiently find the best solutions for all possible combinations of cities. But in 1976, Nicos Christofides developed an algorithm that efficiently finds approximate solutions – cycles that are more than 50 percent longer than the best cycles. At that time, computer scientists expected that someone would soon improve the simple algorithm of Christofides and come up with a real solution. But the expected progress did not come.
“Many people spend countless hours trying to improve this result,” said Stanford University’s Amin Saberi.
Today, Karlin, Klein and Oveis Gharan have proven that an algorithm created a decade ago beats Christofides’ 50 percent factor, although they have only managed to reduce 0.2 billion trillion by one percent. However this minuscule contraction enters into both theoretical logjam and a psychological one. Researchers expect it to open up yards for further improvement.
“It was a result I wanted all my career,” said David Williamson of Cornell University, who has been studying travelperson travel problems since 1980.
The salesperson’s traveling problem is one of the few foundation problems that computer theoretical scientists repeatedly turn to to test the limits of efficient calculation. The new result “is the first step towards showing that the boundaries of good calculation are in fact better than we thought,” Williamson said.
While there is probably no great method that always finds the shortest drive, it is possible to find something as good: the shortest tree that connects all cities, meaning a network of connections (or “edges”) without closed loops. Christofides ’algorithm uses this tree as the backbone for a round trip, adding extra edges to convert it into one round.
Any round trip route should have an equal number of edges in each city, as each arrival is followed by departure. It turns out that the reversal is also true — if every city in a network has an equal number of connections then the edges of the network should track a rotation.
The shortest tree connecting all cities does not belong to this equal, since any city at the end of a branch has only one connection to another city. So to make a round the shortest tree, Christofides (who died last year) found the best way to connect pairs of cities with odd numbers of edges. He then proved that the resulting rotation would never be more than 50 percent longer than the best possible rotation.
In doing so, he came up with perhaps the most popular approximation algorithm in computer theoretical science – one that usually forms the first example in textbooks and courses.
“Everyone knows the simple algorithm,” said Alantha Newman of Grenoble Alpes University and the National Center for Scientific Research in France. And when you find out, he says, “you know the state of the art” – at least, you did until last July.