OpenAI model claims tight 1 + 2/e approximation for k-median
Awaiting review
Importance: major (4 of 5)The takeaway
Family 125 of OpenAI’s 722-manuscript release claims a deterministic polynomial-time (1 + 2/e + ε)-approximation for metric k-median, which would settle the problem’s approximability under P ≠ NP. OpenAI lists Lean comparator statements for it; no independent expert check has been published yet.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 15 October 2026
Your AI and this story
- GPT-6 Astra159 days after its cutoff
- Claude Opus 5.598 days after its cutoff
- Gemini 4 Argon189 days after its cutoff
- Grok 4.7128 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 98 days before it.
Key facts
- Source: OpenAI’s math repository, CONTENTS.md family 125: ‘Gives a deterministic polynomial-time (1+2/e+ε)-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming P≠NP, the optimal infimum approximation factor is 1+2/e.’
- Manuscripts (both dated Sept 24, 2026): ‘The approximation threshold for metric k-median’ and ‘Single-exponential recovery and bounded-price strictness for metric k-median’; the second also gives a randomized (2 − σ)-approximation for an absolute σ > 0
- Lean: lean/docs/125.md lists four comparator statements (MetricKMedian, KMedianThreshold, KMedianRecovery, KMedianRefinedRecovery); MetricKMedian.lean states the result with Lean’s TM2ComputableInPolyTime (a polynomial-time Turing-machine algorithm), permitted axioms propext, Quot.sound and Classical.choice; the solution module OAI.Combinatorics.KMedian has about 1,300 files (repo tree, Oct 15)
- Context: k-median cannot be approximated below 1 + 2/e in polynomial time unless P = NP (Guha–Khuller / Jain–Mahdian–Saberi); before October 2026 the best guarantees were (2 + ε) (Cohen-Addad et al. 2025; Byrka et al. 2026), as summarised in arXiv 2610.18144
- Concurrent human work: arXiv 2610.18144 (EPFL, Google Research, CMU, NYU; Oct 13) reaches better than 2 and describes OpenAI’s (1 + 2/e + ε) algorithm as extending Byrka et al.’s iterative rounding; a group around Jarosław Byrka and Shi Li independently reached 2 − σ
- Production: per the repo README, most results came from an unreleased internal OpenAI model, about three hours of ChatGPT Pro thinking compute per result, from about 4,000 posed problems
- Verification status: OpenAI’s own Lean formalization; no referee report, expert blog post or independent build check found as of Oct 15
What happened
OpenAI’s Oct 6, 2026 release of model-written mathematics (github.com/openai/math) includes a family of two k-median papers dated Sept 24. The headline claim is a deterministic polynomial-time algorithm that, for any fixed ε > 0, finds k facilities whose total client distance is within (1 + 2/e + ε) of the optimum. Approximating k-median below 1 + 2/e is NP-hard, so if correct this settles the problem’s approximation ratio in the model with specified candidate facilities. A companion paper gives a randomized (2 − σ)-approximation through a recovery argument.
OpenAI’s Lean catalogue links four “comparator” statements for the family. The main one, MetricKMedian.lean, states the algorithm’s
existence and polynomial running time formally in Lean (via Mathlib’s Turing-machine complexity definitions). The proof module is large,
about 1,300 Lean files.
The result received little attention in the first week. It surfaced through the EPFL-led paper of Oct 13 (arXiv 2610.18144), whose own human-proved algorithm breaks factor 2 and which mentions the OpenAI work as concurrent. No independent expert has yet published an assessment of the OpenAI proofs or checked the formalization build.
Why it matters
Closing the gap between the 1 + 2/e lower bound and the factor-2 upper bound for k-median was a well-known open question in approximation algorithms. A formalized, model-generated answer would be one of the strongest computer-science items in OpenAI’s release, but it has the same caveats as the rest: self-published, unrefereed, and checked so far only by OpenAI’s own Lean work.
What is disputed or not yet verified
| Verification | Lean formalization by OpenAI (comparator statements published); not yet independently checked or refereed |
|---|
Sources
4 sources from 2 sites. Numbers match the chips in the text.
4 sources: 4 primary
Primary
- OpenAI math repository: CONTENTS.md (family 125, metric k-median)github.com, code
- OpenAI math repository: Lean scope note for family 125github.com, code
- Lean comparator statement: MetricKMedian.leangithub.com, code
- arXiv 2610.18144: A Better-than-2 Approximation for k-Median Part I (cites OpenAI’s result as concurrent work)arxiv.org, paper
Also cited in the text
Changes
- Filed from data/leads.md (Lean docs and comparator file read via GitHub)