The Asymmetric Traveling Salesman Problem is harder than its symmetric cousin. When the cost of traveling from A to B can differ from B to A, the structural properties that enable good approximation algorithms break down. The best known approximation ratio has been stubbornly large — orders of magnitude worse than the symmetric case's 3/2-approximation.
Jens Vygen brings it below 15.
The improvement is on one of the most studied problems in combinatorial optimization. The ATSP has resisted the techniques that cracked symmetric TSP: there's no analog of Christofides' algorithm, because the asymmetric minimum spanning tree doesn't shortcut the way the symmetric one does. Instead, progress has come through thin tree decompositions and LP relaxation bounds, with each improvement requiring a new structural insight about the relationship between the LP solution and the optimal tour.
The LP relaxation is the natural linear programming formulation: minimize tour cost subject to subtour elimination constraints. The integrality gap — the worst-case ratio between the LP optimum and the true optimum — is the fundamental barrier. Vygen proves improved upper bounds on this gap, which translate directly into improved approximation guarantees.
The result also covers two variants: unweighted digraphs (where all edge costs are 0 or 1) and the open tour problem (minimum-cost path with given distinct endpoints). Both get tighter ratios from the same framework.
Fifteen is still far from optimal. For symmetric TSP, the approximation ratio is 3/2 and the integrality gap of the Held-Karp relaxation is conjectured to be 4/3. For ATSP, the gap between best upper and lower bounds is still wide. But each drop in the ratio requires overcoming a barrier that the previous bound couldn't clear. The problem doesn't yield easily, and each inch matters.