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.
Now Karlin, Klein and Oveis Gharan have proved that an algorithm devised a decade ago beats Christofides’ 50 percent factor, 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 that it will open the floodgates to further improvements.
“This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s.
The traveling salesperson problem is one of a handful of foundational problems that theoretical computer scientists turn to again and again to test the limits of efficient computation. The new result “is the first step towards showing that the frontiers of efficient computation are in fact better than what we thought,” Williamson said.
Fractional Progress
While there is probably no efficient method that always finds the shortest trip, it is possible to find something almost as good: the shortest tree connecting all the cities, meaning a network of connections (or “edges”) with no closed loops. Christofides’ algorithm uses this tree as the backbone for a round-trip tour, adding extra edges to convert it into a round trip.
Any round-trip route must have an even number of edges into each city, since every Computer scientists have long suspected that there should be an approximation algorithm that outperforms Christofides’ algorithm. After all, his simple and intuitive algorithm isn’t always such an effective way to design a traveling salesperson route, since the shortest tree connecting the cities may not be the best backbone you could choose. For instance, if this tree has many branches, each city at the end of a branch will need to be matched with another city, potentially forming lots of expensive new connections.
In 2010, Oveis Gharan, Saberi and Mohit Singh of the Georgia Institute of Technology started wondering if it might be possible to improve on Christofides’ algorithm by choosing not the shortest tree connecting all the cities, but a random tree from a carefully chosen collection. They took inspiration from an alternate version of the traveling salesperson problem in which you are allowed to travel along a combination of paths—maybe you get to Denver via 3/4 of the route from Chicago to Denver plus 1/4 of the route from Los Angeles to Denver.
Unlike the regular traveling salesperson problem, this fractional problem can be solved efficiently. And while fractional routes don’t make physical sense, computer scientists have long believed that the best fractional route should be a rough guide to the contours of good ordinary routes.
So to create their algorithm, Oveis Gharan, Saberi and Singh defined a random process that picks a tree connecting all the cities, so that the probability that a given edge is in the tree equals that edge’s fraction in the best fractional route. There are many such random processes, so the researchers chose one that tends to produce trees with many evenly connected cities. After this random process spits out a specific tree, their algorithm plugs it into Christofides’ scheme for matching cities with odd numbers of edges, to convert it into a round trip.
No comments:
Post a Comment