This is the fifth and final post in a series that began here and continued here, here, and here. The series presents one striking and accessible theorem associated with each of the 2026 Fields Medalists and with the 2026 Abacus Medalist. This final post concerns Abacus Medalist Shayan Oveis Gharan and his work on the famous travelling salesman problem.
Let be a graph in which every edge joining vertices and has a non-negative length . We seek the shortest closed route that visits every vertex of . Naturally, we assume that is connected, since otherwise no such route exists.
We may pass to the metric completion of : take the complete graph on the same vertex set and define the length of the edge from to to be the length of a shortest path between them in the original graph. The resulting edge lengths satisfy the triangle inequality Conversely, an edge in the completed graph can always be replaced by a corresponding shortest path in the original graph. Thus this transformation does not change the answer to the problem.
Once the triangle inequality holds, repeated visits to a vertex can be removed by shortcutting the tour, without increasing its length. We may therefore look for a shortest closed tour that visits every vertex exactly once: a shortest Hamiltonian cycle. This is the metric travelling salesman problem, or TSP.
In the 1970s, Christofides (Christofides 1976) and Serdyukov (Serdyukov 1978) developed a polynomial-time algorithm that finds a Hamiltonian cycle of length at most where denotes the length of an optimal tour. In 2015, Karpinski, Lampis, and Schmied (Karpinski et al. 2015) proved that it is NP-hard to approximate to any factor smaller than . Hence, if denotes the best approximation ratio achievable in polynomial time, then
For more than four decades, nobody was able to improve the upper bound of . This led some researchers to suspect that the Christofides–Serdyukov ratio might be optimal. In 2024, however, Karlin, Klein, and Oveis Gharan (Karlin et al. 2024) disproved this conjecture.
To understand the new result, it is useful first to recall the Christofides–Serdyukov algorithm. The algorithm begins by finding a minimum spanning tree of . It then considers the vertices of odd degree in and adds a minimum-cost perfect matching between them. Every vertex in the resulting multigraph has even degree, so the multigraph has an Eulerian circuit. Traversing this circuit and shortcutting repeated vertices produces a Hamiltonian cycle.
The approximation guarantee comes from two simple estimates. The minimum spanning tree has length at most , because deleting any edge from an optimal tour leaves a spanning tree. The matching on the odd-degree vertices has length at most . Consequently, the final tour has length at most
The algorithm of Karlin, Klein, and Oveis Gharan modifies this construction by choosing a random spanning tree from a carefully designed probability distribution and then repairing its odd-degree vertices with a minimum-cost matching. The central difficulty is to prove that the random tree and its matching are, in expectation, just slightly cheaper than the worst case allowed by the classical analysis.
The numerical improvement in Theorem is extraordinarily small, so the stated bound has little direct practical significance. The algorithm itself may nevertheless perform much better on typical instances: no examples are known on which its approximation ratio is worse than . More importantly, the theorem is theoretically decisive. It proves that is not an insurmountable barrier and opens the way to further progress on one of the most celebrated problems in combinatorial optimization.