salesman has to visit every major city in the U.S. 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.