The approximation threshold for metric -median: is attainable?
In metric -median, finite sets of clients and candidate facilities lie in a common metric space, and one opens at most facilities to minimize the total distance from clients to their nearest open facility. Approximating within any factor below is NP-hard in this candidate-facility model, by the Max--Coverage gap. Algorithms improved from the first constant factor (Charikar-Guha-Tardos-Shmoys) through local search (Arya et al.), Li-Svensson's route past factor three, (Byrka et al.) and (Gowda et al.) to (Cohen-Addad et al., announced 2025). Is there, for every , a polynomial-time -approximation, so that is the exact approximation threshold?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Approximation algorithms; clustering
- Posed by
- Implicit in the 1+2/e hardness bound of Jain, Mahdian and Saberi (2002); the manuscript names no poser
- Year posed
- —
- Years open
- —
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 42 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: for every fixed , a deterministic algorithm running in time polynomial in the binary input length (the polynomial depends on ) returns with and cost at most , for arbitrary and arbitrary finite rational metrics with specified candidate facilities. Corollary 1.2: under , the infimum of polynomial-time approximation factors in this model is , the lower bound being the known coverage gap. It does not give a -approximation itself, does not settle the model where every client is a candidate facility (), whose lower bound differs, and claims no practical running time. The companion proves a randomized -approximation for an absolute by anchor recovery and bounded-price payment accounting.
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with one fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author. A companion manuscript of the same date (single-exponential recovery and bounded-price strictness) gives an independent randomized approximation below factor two and is cited by the principal paper.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.1 and Corollary 1.2 of the principal manuscript were read against the question. lean/docs/125.md lists four challenges; two cover this entry: ComparatorChallenges/MetricKMedian.json (theorem OAI.MetricKMedian.main_finite_work, solution module OAI.Combinatorics.KMedian.Main) and KMedianThreshold.json (OAI.MetricKMedian.threshold, module OAI.Combinatorics.KMedian.Threshold). Both solution files exist at the pinned commit, and neither challenge is in the formalization catalogue formalization.yaml (only the companion's KMedianRecovery is). The statements were read here: for every a polynomial-time Turing machine with finite alphabets outputs a nonempty set of at most candidate facilities of cost at most on every finite rational instance; and, from a formalized , the infimum of deterministic polynomial-time factors is exactly , so the hardness side is formalized too. That is the headline claim. Not rebuilt here. The threshold is an infimum: attaining itself is not claimed, and the model is a different question.