The metric k-median approximation threshold and recovery

The best possible guarantee for placing k facilities is exactly 1 + 2/e, assuming P ≠ NP.

2 papers September 24, 2026 Explained by AI

In metric k-median you open at most k facilities to make clients' total distance to the nearest one smallest. Fast methods can only promise to land within some factor of the best total. Before this work that factor was about 2, and nothing below about 1.736 was possible unless P = NP. This paper proves a fast method for every factor above 1 + 2/e, about 1.736 (Lean proof listed). So 1 + 2/e is exactly the best possible factor, assuming P ≠ NP.

First step

2002

Charikar, Guha, Tardos and Shmoys, first constant-factor approximation

Significance

Major

If it holds, it settles the best possible guarantee for a classic clustering problem. It closes the gap between about 1.736 and 2.

Trust

Formal proof listed

Field

Theoretical computer science

2 papers

Best proven approximation factor for metric k-median

Year	Who	Value
2004	Arya et al.	3
2017	Byrka et al.	2.675
2023	Gowda et al.	2.613
2025	Cohen-Addad et al.	2
2026	This paper	1.736

Smaller is better. Below 1 + 2/e ≈ 1.736 is impossible unless P = NP. Values ignore the small + ε.

The explanation

Picture a town with four houses and three possible clinic sites, A, B and C. The town can afford two clinics. Site A is close to houses 1 and 2. Site B is close to houses 3 and 4. Site C is close to houses 2 and 3. Close means a distance of 1, and far means a distance of 3. Each house uses its nearest open clinic. The town wants the smallest total travel distance.

There are only three ways to pick two sites. A and B give every house a close clinic, so the total is 4. A and C leave house 4 far away, so the total is 6. B and C leave house 1 far away, also 6. The best plan costs 4. The worst costs 1.5 times as much. This is the metric k-median problem. The k is the number of clinics allowed, here 2. Metric means the distances behave like real distances: a detour through a third point is never shorter.

Real instances have thousands of points, and trying every choice takes far too long. So researchers look for fast methods with a guarantee. Fast here means polynomial time: the running time grows like a fixed power of the input size. The guarantee is an approximation factor. A factor of 2 means the method's total is never more than twice the best total.

Charikar, Guha, Tardos and Shmoys gave the first fast method with a fixed factor, published in 2002. A local search method of Arya and coauthors reached 3 plus ε in 2004. Here ε means any small positive number chosen in advance. In 2016, Li and Svensson showed that a few extra clinics can later be removed at a tiny extra cost. That opened a route past factor 3. Byrka and coauthors reached 2.675 plus ε. Gowda and coauthors reached 2.613 in 2023. Cohen-Addad and coauthors reached 2 plus ε, first announced in 2025.

There is also a floor, and the town example shows where it comes from. Suppose every site is either close or far from every house. If the chosen sites leave c of m houses close, the total is 3m − 2cSource 1. A perfect choice gives m. Uriel Feige's 1998 work on covering problems supplies a hard case, assuming P ≠ NPSource 2. That is the standard belief that some problems with easy-to-check answers have no fast solution. Under it, no fast method can tell apart two cases. In one, a perfect choice exists. In the other, every choice leaves about 36.8 percent of houses far. That share is 1/e, where e is about 2.71828. The second case has a total of at least about 1.7358m, or 1 + 2/e times m. So no fast method can promise a factor below 1 + 2/eSource 3 Source 4. That left a gap between about 1.7358 and 2.

The hard part is the clinic budget. A low total is much easier to reach when a few extra clinics are allowedSource 5. A 2026 graph-based rounding method also reached 2 plus ε. Its general transfer step stalls at factor 2 for this problemSource 6. This paper keeps the extra-clinics route. It first allows a fixed number of extra clinics, then removes them with the Li and Svensson stepSource 7. Its new ingredient is a sharper way to compare costs while partial choices are rounded into whole onesSource 8. That comparison is what gets below 2.

This paper proves the matching upper bound (Lean proof listed). For every fixed ε, a fast method opens at most k sitesSource 9. Its total stays within 1 + 2/e + ε times the best. It is deterministic: it uses no coin flips and gives the same answer every runSource 9. Together with the floor, the best possible factor is exactly 1 + 2/e, assuming P ≠ NP. Back in the town, the best total is 4. So the method's total is at most about 6.94, plus a sliver for ε. No fast method can promise to beat 1 + 2/e on every town.

The result has limits worth keeping in view. It does not give a method with factor exactly 1 + 2/eSource 10. Each ε gets its own method, and the power in its running time may depend on εSource 11. The candidate sites are listed separately from the houses. The version where clinics must sit at houses is a different questionSource 12. A companion paper gives a separate method that flips coins and beats factor 2 by a fixed amountSource 13. Its proof does not use the main paper's rounding argumentSource 14.

How sure is this? A computer proof checker called Lean has checked formal versions of four statements. Two are the deterministic 1 + 2/e + ε method and the exact threshold assuming P ≠ NP. The other two are the companion's coin-flipping method and its recovery theorem. Each has a Comparator statement listed. No specialist review has been published yet.

What it doesn't show. This does not give a method that reaches factor 1 + 2/e itself. It also leaves open the version where facilities must sit at clients.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proofs hold. Lean formalizations are listed for the main statements. Still, the threshold assumes P ≠ NP, and the guarantee holds only above 1 + 2/e. No specialist review has been published.

Words used

Metric k-median: Choose at most k facilities from a list so that the total distance from clients to their nearest chosen facility is smallest.
Metric: A way of measuring distance where a detour through a third point is never shorter than going direct.
Polynomial time: A running time that grows like a fixed power of the input size; this is what fast means here.
Approximation factor: A promise that a method's total is never more than this many times the best possible total.
P ≠ NP: The widely believed conjecture that some problems with easy-to-check answers have no fast solution.
Deterministic: A method that uses no random choices and gives the same answer every time.
Threshold: The exact boundary: every factor above it is reachable by a fast method, and none below it is, under P ≠ NP.

The original papers (2)

Single-exponential recovery and bounded-price strictness for metric k-median (PDF, opens in a new tab)
September 24, 2026 Formal proof listed
The approximation threshold for metric k-median (PDF, opens in a new tab)
September 24, 2026

Lean notes

All quoted lines (14)

For a universe of size $m$ , the connection cost is exactly $3m-2c$ when the chosen sets cover $c$ elements; a perfect cover has cost $m$ .
The approximation threshold for metric k-median Back to text
We use the formulation under $P\ne NP$ recorded by Anand and Lee, based on Feige's perfect-completeness coverage gap.
The approximation threshold for metric k-median Back to text
Thus a gap between covering every element and covering at most a $1-1/e+\delta$ fraction gives the lower bound $1+2/e-2\delta$ , for every fixed positive $\delta$ .
The approximation threshold for metric k-median Back to text
If $P\ne NP$ , the infimum of deterministic polynomial-time approximation factors for metric $k$ -median with specified candidate facilities is $1+2/e$ .
The approximation threshold for metric k-median Back to text
The facility budget is a central difficulty: a solution with small connection cost can be much easier to obtain when extra facilities are allowed.
The approximation threshold for metric k-median Back to text
The earlier framework's general transfer theorem uses a parameter at least $2$ in the metric $k$ -median case; it does not supply the smaller factor proved here.
The approximation threshold for metric k-median Back to text
Our approach first permits a constant additive surplus, makes that approximation deterministic, and then removes the surplus using an established reduction.
The approximation threshold for metric k-median Back to text
Our construction follows the iterative graph framework, with the cost analysis replaced by a directed comparison inequality and a potential that retains some surviving assignments after an opening.
The approximation threshold for metric k-median Back to text
For every fixed $\varepsilon>0$ , there is a deterministic algorithm which, given a finite rational metric $k$ -median instance with $1\le k\le |F|$ , returns $S\subseteq F$ , $|S|\le k$ , such that $\sum_{j\in J}d(j,S)\le \left(1+\frac2e+\varepsilon\right)\OPT_k.$
The approximation threshold for metric k-median Back to text
The infimum in Corollary … does not assert attainment of the endpoint factor.
The approximation threshold for metric k-median Back to text
The polynomial may depend on $\varepsilon$ .
The approximation threshold for metric k-median Back to text
In particular, the corresponding lower-bound question with the restriction $F=J$ is different.
The approximation threshold for metric k-median Back to text
A separate companion combines anchor recovery with bounded-price payment accounting to give an independent randomized approximation below factor $2$ while respecting the facility budget.
The approximation threshold for metric k-median Back to text
The recovery, execution and global application proofs below are independent of that graph-rounding argument.
Single-exponential recovery and bounded-price strictness for metric k-median Back to text