k-median at 1 + 2/e?

0:00Metric k-median

Pick at most k facilities from a list of candidates, so that the total distance from every client to its nearest open facility is as small as possible. That is metric k-median: distances obey the triangle inequality, and the budget k is strict. Finding the optimum is NP-hard, so the question is how close a fast algorithm can get, and there is a floor. Turn a coverage problem into distances: a facility for each set, a client for each element, at distance one when the element is in the set, three when it is not, and two between any two sets or any two elements. Then choosing k sets that cover c of m elements costs exactly 3m − 2c. In our check, the gadget was a metric, and that formula held on all 6,984 choices we tried, across 300 random set systems. Feige’s hardness for maximum coverage implies that, unless P equals NP, no fast algorithm can tell instances where k sets cover everything, at cost m, from those where every choice of k sets leaves nearly a fraction 1/e uncovered, and so costs at least nearly (1 + 2/e) m. So no deterministic polynomial-time algorithm beats 1 + 2/e, about 1.736. Algorithms came down slowly. Charikar, Guha, Tardos and Shmoys gave the first constant factor, Jain and Vazirani used primal-dual methods, and Arya and coauthors reached 3 + ε by local search. Li and Svensson showed that a few extra facilities can be removed at small cost, which took the factor below three, to 1 + √3, about 2.732. Byrka and coauthors’ bi-point rounding then gave 2.675, after a correction, and Gowda and coauthors 2.613. Cohen-Addad and coauthors reached 2 + ε, first announced in 2025, and Byrka and coauthors gave a graph-based iterative rounding with the same factor.

2:06The claims

Result 125 is two OpenAI preprints, both dated September 24. The main one, 46 pages, claims that for every fixed ε there is a deterministic polynomial-time algorithm that opens at most k facilities and pays at most (1 + 2/e + ε) times the optimum, on any finite rational metric with specified candidate facilities. Together with the coverage floor, the best possible factor for deterministic algorithms, unless P equals NP, is then exactly 1 + 2/e, as an infimum: the endpoint itself is not claimed. The degree of the polynomial may depend on ε. The companion, 53 pages, gives a separate route below two, built on Cohen-Addad and coauthors’ algorithm: a recovery algorithm that rebuilds a good solution from an anchor that is accurate on all but logarithmically many clusters, plus a payment argument, together giving a randomized 2 − σ approximation for an absolute constant σ. The threshold is for this model, where candidate facilities may differ from the clients; when facilities must sit at clients, the lower-bound question is different. OpenAI published Lean formalizations of the four main statements, about 1,280 files and 142,000 lines with their imports, not counting Mathlib. For the threshold, the Lean proof also derives the hardness side from P not equal to NP, with its own modules for the Cook–Levin theorem, expanders and gap amplification. We have not run the Lean check ourselves.

3:48How the algorithm works

The algorithm starts from the standard linear program, which opens fractions of facilities, with total opening at most k and cost at most the optimum. It rounds the openings to multiples of a small grid, 1/Δ, so that each opening is a stack of small copies. Separated representative clients gather nearby opening mass into bundles, and each bundle’s missing part is rounded together with its suppliers, which keeps both the budget and the cost of restoring a full unit under control. The total opening grows by at most 3 grid units. Then come rounds. In each round, a random directed graph says which copies are erased when a given copy’s facility opens: every target has exactly Δ incoming sources, chosen with probabilities that taper off with distance. Opening and erasing are balanced, and a source that would erase too much is simply forced open, so, apart from rare runs that are thrown away, only a constant number of extra facilities is needed. This source-opening and neighbor-erasure framework builds on the iterative rounding of Byrka and coauthors. The cost analysis is new. For each client, it tracks the surviving copies of its original unit and a persistent bound on its final distance, combined into a potential whose coefficient depends on elapsed time. The key function is A(x) = 1 + 2∫₀¹ (1 − e^(−tx)) dt. The process starts at x = 1, where A is exactly 1 + 2/e, so each client’s potential starts at (1 + 2/e) times its fractional cost, and on average it barely grows; that starting value is the factor. A finite comparison inequality, with no symmetry assumed, bounds the potential’s drift, and its scalar estimates are proved with exact polynomial certificates. In our check, the five scalar bounds of Lemma 4.2 held at every one of about 380,000 grid points we tried, some with no room to spare: a few become exact equalities at the edges of their range. Only a few low-order moments of each random choice enter the analysis. So each random step is replaced by a small exact distribution with the same moments, found by a Carathéodory elimination; all histories for a constant number of rounds are expanded, and the cheapest outcome within that budget is kept. That gives a deterministic algorithm opening at most k plus a constant number of facilities, and Li and Svensson’s reduction removes the surplus at an arbitrarily small extra loss. In our check, exact elimination reduced a distribution on 40 states with 4 features to 5 states with the same expectations.

6:40Where it stands

The preprints are not peer reviewed and have not been revised. The Lean formalizations cover the main theorem, the threshold under P not equal to NP, and both statements of the companion; we have not run them. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If they hold, metric k-median with candidate facilities is settled up to ε: 1 + 2/e is the exact limit for deterministic polynomial-time approximation, unless P equals NP. The algorithm is a theoretical one, with a polynomial whose degree may depend on ε.