How Good Can a TSP Approximation Get?

The traveling salesman problem asks for the shortest possible route that visits every city in a list exactly once and returns to the start. It’s a classic NP-hard problem: nobody can solve it exactly and efficiently for large instances (unless P = NP), so research instead asks how close a fast algorithm can get to the true optimum. For “metric” TSP — where distances satisfy the triangle inequality, as ordinary geographic distances do — that’s exactly what the metric TSP approximation frontier tracks.

Forty-four years at 3/2

In 1976, Nicos Christofides described an algorithm — built from a minimum spanning tree, a minimum-weight perfect matching, and an Eulerian shortcut — that is guaranteed to find a tour no more than 1.5× the length of the optimal tour, for any metric instance. That 3/2 approximation ratio stood as the best proven guarantee for the problem for 44 years, long enough that many in the field suspected it might be the true answer.

The frontier finally moved

In 2020, Anna Karlin, Nathan Klein, and Shayan Oveis Gharan gave a randomized algorithm that beats Christofides’ ratio, guaranteeing a tour of length at most (3/2 − ε) times optimal for some fixed, tiny ε > 0. The improvement over 3/2 in the original result is astronomically small — far too small to matter for any real route-planning problem — but it proved something Christofides’ bound alone never could: that 3/2 is not the best possible worst-case guarantee for a polynomial-time algorithm.

Why a tiny improvement is still a big result

In complexity theory, the size of an improvement matters far less than whether the barrier moves at all. A 44-year-old bound resisting an enormous amount of effort, then finally breaking by any nonzero margin, tells researchers the wall wasn’t fundamental — there was room to improve, and the gap between the algorithmic upper bound and the P≠NP-based theoretical lower bound (below 3/2, but not by much) is not yet closed.

Why it’s here

TSP approximation is a clean example of the Registry’s two-sided-bound format applied to an algorithm rather than a physical quantity: the exact optimum is out of reach for large instances, but the best guaranteed approximation ratio is itself a real, trackable frontier that has already moved once and could move again.

Primary source

Karlin, Klein & Oveis Gharan, “A (Slightly) Improved Approximation Algorithm for Metric TSP” ↗