When Nathan Klein started his graduate studies two years ago, his advisers came up with a modest plan: to work together on one of the best-known and oldest problems in theoretical computing.
Even if they couldn’t figure it out, they figured Klein would learn a lot. He accepted the idea. “I didn’t know how to be intimidated,” he said. “I was just a freshman – I don’t know what’s going on.”
Now in a article uploaded in July, Klein and his University of Washington advisers Anna Karlin and Shayan Oveis Gharan finally achieved a goal pursued by computer scientists for nearly half a century: a better way to find rough solutions to the problem of itinerant sellers.
This optimization problem, which seeks the shortest (or cheapest) round-trip trip through a set of cities, has applications ranging from DNA sequencing to carpooling logistics. Over the decades, it has inspired many of the most fundamental advances in computing, helping to highlight the power of techniques such as linear programming. But researchers have yet to fully explore its possibilities – and not for lack of trying.
The itinerant salesperson problem “is not a problem, it’s an addiction,” as Christos Papadimitriou, a great expert in IT complexity, likes to say.
Most computer scientists believe that there is no algorithm capable of effectively finding the best solutions for all possible combinations of cities. But in 1976, Nicos Christofides proposed an algorithm that efficiently finds rough solutions – round trips that are at most 50% longer than the best round trip. At the time, IT people expected someone to improve Christofides’ simple algorithm soon and get closer to the real solution. But the expected progress has not arrived.
“A lot of people have spent countless hours trying to improve this result,” said Amin Saberi of Stanford University.
Now, Karlin, Klein, and Oveis Gharan have proven that an algorithm designed ten years ago beats Christofides’ 50% factor, although they could only subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this tiny improvement breaks both a theoretical and psychological blockage. Researchers hope this will open the floodgates for further improvements.
“This is the outcome that I’ve wanted my entire career,” said David Williamson of Cornell University, who has been studying the issue of traveling salespeople since the 1980s.
The roaming vendor problem is one of the few fundamental problems that theoretical computer scientists turn to over and over again to test the limits of efficient computing. The new result “is the first step in showing that the boundaries of efficient computing are actually better than we thought,” Williamson said.
While there is probably no efficient method that always finds the shortest route, it is possible to find something as good: the shortest tree connecting all the cities, that is say 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 to a round trip.
Any round trip route must have an even number of edges in each city, as each arrival is followed by a departure. Turns out, 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 shortest tree connecting all the cities does not have this regularity property, since any city at the end of a branch has only one connection to 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. Then he proved that the resulting round trip would never be more than 50% longer than the best possible round trip.
In doing so, he designed perhaps the most famous approximation algorithm in theoretical computing – one that is usually the first 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 it, she said, “you know the state of the art” – at least you did until last July.