Approximation ratio 3/2 for the metric TSP is not optimal

You need to know: Algorithms and their running time, polynomial algorithm, probabilistic algorithm, basic graph theory, complete graph, hamiltonian cycle.

Background: The metric travelling salesman problem (TSP) asks to find a hamiltonian cycle (also called TSP tour) of minimum weight in a compete graph with non-negative edge weights.

The Theorem: On 2nd July 2020, Anna Karlin, Nathan Klein and Shayan Gharan submitted to arxiv a paper in which they proved that there exists a constant and a randomized algorithm that outputs a TSP tour with expected weight at most times the weight of the optimal tour. In fact, one can take .

Short context: The TSP is one of the most-studied problems in the theory of algorithms. In 1970-th, Christofides and Serdyukov developed a polynomial time algorithm which finds a hamiltonian cycle of weight at most times the optimal one. Because the Christofides-Serdyukov algorithm has been unimproved for over 40 years, some people started to conjecture that the approximation ratio is optimal for polynomial-time algorithms. The Theorem disproves this conjecture.

Links: The free version of the original paper is available here.

Go to the list of all theorems