A salesman has to visit every major city in the United States. What is the cheapest way to hit them all exactly once and then return to the headquarters? The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible. Nevertheless, computer scientists have long known how to find a pretty good route—one that incurs no more than 1.5 times the optimal cost.
The traveling salesman problem assumes that a trip between any two cities will cost the same going in either direction. But that’s often not the case. For example, perhaps a flight from Chicago to Denver is cheaper (or takes less time) than the flight from Denver to Chicago. Finding the optimal flight path under these conditions—known as the asymmetric traveling salesman problem—is also computationally infeasible. But unlike when solving the plain vanilla traveling salesman problem, researchers didn’t know how to find a near-optimal route for a trip to a large number of cities. That is, until last month, when three computer scientists announced that they had devised an approximation algorithm that remains efficient in all cases.
Why is the asymmetric traveling salesman problem so hard? In short, when routes are more expensive in one direction than they are in the other, there are many more routes to consider. The added difficulty meant that, until now, all algorithms for solving the asymmetric traveling salesman problem would either take too long or result in unusable routes. The new algorithm thus “solves a long-standing open problem and is a breakthrough of the first order,” wrote Ken Regan of the University at Buffalo and Dick Lipton of Georgia Tech on Gödel’s Lost Letter and P=NP, a blog on contemporary algorithms research.
“The first time I thought about the problem was during my Ph.D. in 2008,” said Ola Svensson, one of the three authors of the new paper. After seven years of hacking away at the problem, Svensson came up with a solution for a simpler problem of lumping cities together into groups and visiting at least one city from each group.
Svensson then enlisted Jakub Tarnawski and László Végh, his coauthors, to help him develop a new algorithm that repeatedly forms smaller subgroups within the groups of cities until it identifies cheap routes within each group. The routes within the groups are then patched together, using Svensson’s previous research, to construct a full route. While previous attempts at solving the asymmetric traveling salesman problem used similar approaches, none of them were successful at locating the groups of cheap routes that can be patched together.
While the paper has not been peer reviewed yet, Regan said it has a good chance of withstanding the computer science community’s scrutiny. “The ideas in the proofs are very clear,” Regan said. “There is one potential sensitive [technical] point … [but] very solid, very promising, well structured, and well broken-out.”
Svensson said he and his coauthors planned to submit their paper to an upcoming conference—the 50th annual Symposium on the Theory of Computing—for formal peer-reviewing.
