When Nathan Klein started graduate school two years ago, his advisors proposed a modest plan: to work together on one of the most famous, long-standing problems in theoretical computer science.
Although they did not manage to solve it, they reckoned that Klein would learn a lot in the process. He followed the idea. “I did not know I was scared,”
In a paper published online in July, Klein and his advisers at the University of Washington, Anna Karlin and Shayan Oveis Gharan, have finally reached a goal that computer scientists have been pursuing for nearly half a century: a better way to find approximate solutions on the problem of the traveling seller.
This optimization problem, which seeks the shortest (or cheapest) 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 and helped illuminate the power of techniques such as linear programming. But researchers have not yet fully explored the possibilities – and not for lack of experimentation.
The problem with the traveling seller “is not a problem, it’s an addiction,” as Christos Papadimitriou, a leading expert in computational complexity, is happy to say.
Most computer scientists believe that there is no algorithm that can effectively find the best solutions for all possible combinations of cities. But in 1976, Nicos Christofides came up with an algorithm that effectively finds approximate solutions – return trips that are no more than 50 percent longer than the best return flight. At the time, computer scientists expected that someone would soon improve Christofides’ simple algorithm and get closer to the true solution. But the expected progress did not arrive.
“A lot of people spent countless hours improving this result,” said Amin Saberi of Stanford University.
Now, Karlin, Klein and Oveis Gharan have proven that an algorithm devised a decade ago beats Christofides’ 50 percent factor, even 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 it will open the river gates for further improvements.
“This is a result that I have wanted for my entire career,” said David Williamson of Cornell University, who has been studying the issue of travel sales since the 1980s.
The traveling sales problem is one of a handful of fundamental problems that theoretical computer scientists turn to over and over again to test the limits of effective calculation. The new result “is the first step towards showing that the limits of effective calculation are actually better than we thought,” said Williamson.
While there is probably no effective method that always finds the shortest turn, it is possible to find something almost as good: the shortest tree that connects all the cities, meaning a network of connections (or “edges”) without closed loops. Christofides’ algorithm uses this tree as the backbone of a tour and adds extra edges to convert it into a tour.
Each round trip must have an equal number of edges to each city, as each arrival is followed by a departure. It turns out that the reverse is also true – if each city in a network has an equal number of connections, the network edges must track a return flight.
The shortest tree that connects all cities lacks this evenness property, as every city at the end of a branch has only one connection to another city. To turn the shortest tree into a round trip, Christofides (who died last year) found the best way to connect pairs of cities that have odd numbers of edges. He then proved that the resulting return flight will never be more than 50 percent longer than the best possible return journey.
Thus, he devised perhaps the most famous approximation algorithm in theoretical computer science – one that usually constitutes 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 know it, she said, “you know the latest technology” – at least you did until last July.