Browse › Theoretical computer science › 125 The metric k-median approximation threshold and recovery
The approximation threshold for metric k-median
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every fixed ε > 0, we give a deterministic polynomial-time $(1+2/e+\varepsilon)$-approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under $P\ne NP$, the infimum approximation factor in this model is therefore $1+2/e$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-23) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Buhai, Cohen-Addad, Fleischmann, Gupta, Jubés Monforte, Pittu, Stouras, Svensson, Vogl, A Better-than-2 Approximation for k-Median Part I: The Power of General Bids (arXiv:2610.18144, 13 October 2026). An independent randomized polynomial-time 1.95-approximation for k-median; its "AI Acknowledgment and Concurrent Work" paragraph describes the OpenAI result that extends iterative rounding to a $(1+2/e+\varepsilon)$-approximation as concurrent work announced on 6 October 2026. [family-level]
- Buhai, Cohen-Addad, Fleischmann, Gupta, Jubés Monforte, Pittu, Stouras, Svensson, Vogl, A Better-than-2 Approximation for k-Median Part II: Stable Instances (arXiv:2610.17172, 12 October 2026). The companion paper (a $(1.89+\varepsilon)$-approximation for β-stable instances) calls the iterative-rounding OpenAI paper "an optimal" $(1+2/e+\varepsilon)$-approximation in its concurrent-work discussion. [family-level]
Comments and discussion
- Ola Svensson (@AlgoSvensson), post on X (2026-10-07). The original post says OpenAI "completely solved a problem on which my students have worked hard for 1+ years" and that the group will upload a different algorithmic approach. [family-level]
- Ola Svensson (@AlgoSvensson), post on X (2026-10-07). The post says the tight k-median approximation implies a tight result for facility location, an optimal opening-cost versus connection-cost tradeoff, a "pretty well-known connection but not stated in the OpenAI paper".
Formalization
- OpenAI math release, Lean scope notes for family 125 (lean/docs/125.md, 2026). The release's Lean scope note covers the deterministic polynomial-time $1+2/e+\varepsilon$ approximation on finite rational metrics with specified candidate facilities and, assuming $P\ne NP$, the exact infimum threshold $1+2/e$; comparator files are MetricKMedian.lean and KMedianThreshold.lean. [family-level]
Related prior literature mentioned by others
- Jarosław Byrka, Yuhao Guo, Yang Hu, Shi Li, Chengzhang Wan and Zaixuan Wang, k-Clustering via Iterative Randomized Rounding (arXiv:2604.06046, 2026-04-07). Both Buhai et al. papers describe the threshold paper as extending this iterative-rounding $2+\varepsilon$ approach; the paper itself cites it as the framework it builds on.
Possibly relevant literature (found by the agent, not checked)
- Cohen-Addad, Gupta, Kumar, Lee, Li, Tight FPT Approximations for k-Median and k-Means (ICALP 2019, LIPIcs 132, 42:1–42:14). Gives a $(1+2/e+\varepsilon)$ factor for k-median in FPT time, the same factor that Theorem 1.1 claims in polynomial time; the paper's bibliography does not cite it, although the companion paper does.
News and blogs
- Post-Cutoff, OpenAI model claims tight 1 + 2/e approximation for k-median (2026-10-15). This article summarizes both manuscripts, the release's Lean comparator statements, and the concurrent work of Buhai et al. [AI-generated per source] [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 125
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-Approximation-Threshold-for-Metric-k-Median-September-24-2026,
author = {{OpenAI}},
title = {{The approximation threshold for metric $k$-median}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf}{OAI:The-Approximation-Threshold-for-Metric-k-Median-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/125.md. The Lean statements have not been checked by people against the paper's claims.
Family 125: The metric k-median approximation threshold and recovery
Gives a deterministic polynomial-time $(1+2/e+\varepsilon)$-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming $P\ne NP$, the optimal infimum approximation factor is $1+2/e$.
Other papers in this family:
- Single-exponential recovery and bounded-price strictness for metric k-median · September 24, 2026