Browse › Theoretical computer science › 125 The metric k-median approximation threshold and recovery
Single-exponential recovery and bounded-price strictness 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
We give an exact-budget recovery algorithm for metric k-median with single-exponential dependence on the number of comparison clusters without accurate, distinct proxies in a supplied anchor solution. On positive integral metrics of polynomially bounded diameter, a sufficiently small total proxy error and logarithmically many such clusters yield a $(1+2/e+\varepsilon)$ approximation in polynomial time with arbitrarily high success probability. We also prove bounded-price strictness for one compatible execution of the logarithmic-surplus construction. Together the recovery and payment arguments give a randomized $(2-\sigma)$ approximation, for an absolute σ > 0, on arbitrary finite rational metrics, both with high probability and in expectation, while opening at most k facilities on every output.
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 II: Stable Instances (arXiv:2610.17172, 12 October 2026). An independent $(1.89+\varepsilon)$-approximation for β-stable instances; its concurrent-work discussion says the OpenAI stable-instance paper shares "many similarities" with it and achieves $(1+2/e+\varepsilon)$ on stable instances but only $(2-\sigma)$ in general. [family-level]
- 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; it describes the OpenAI $(2-\sigma)$ result as building on the stable-instance and pseudo-approximation framework, much like its own approach. [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]
Formalization
- OpenAI math release, Lean scope notes for family 125 (lean/docs/125.md, 2026). The release's Lean scope note covers the exact-budget refined recovery theorem (under the bounded-integral-metric and accurate-proxy hypotheses) and the randomized $(2-\sigma)$ approximation on finite rational metrics; comparator files are KMedianRefinedRecovery.lean and KMedianRecovery.lean. [family-level]
Related prior literature mentioned by others
- Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn and Ola Svensson, A $(2+\varepsilon)$-Approximation Algorithm for Metric k-Median (arXiv:2503.10972v2, 2026-05-19). Buhai et al.'s concurrent-work discussion identifies this paper's stable-instance/pseudo-approximation framework as the shared basis of the OpenAI recovery paper and their own approach.
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
- Emergent Mind: family 125
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026,
author = {{OpenAI}},
title = {{Single-exponential recovery and bounded-price strictness for metric $k$-median}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026/paper.pdf}{OAI:Single-Exponential-Recovery-and-Bounded-Price-Strictness-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:
- The approximation threshold for metric k-median · September 24, 2026