Theoretical computer science · Result 125

The metric k-median approximation threshold and recovery

2 papersLean

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\).

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 2

Single-exponential recovery and bounded-price strictness for metric k-median

OpenAI · September 24, 2026

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.

Read PDF Download Source

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}
}

The approximation threshold for metric k-median

OpenAI · September 24, 2026

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\).

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The formalization gives an exact-budget recovery algorithm for metric \(k\)-median on the stated polynomially bounded integral metrics. Suppose a supplied anchor represents all but logarithmically many comparison clusters by distinct proxies, with total proxy cost at most the comparison cost plus a sufficiently small relative error. The algorithm always opens at most \(k\) facilities and, with any requested confidence, attains a \((1+2/e+\varepsilon)\) factor relative to those comparison centers in polynomial time.

The linked final approximation result applies to arbitrary finite rational metrics. For one absolute \(\sigma>0\), a polynomial-time fair-bit algorithm always returns a feasible solution, has expected cost at most \((2-\sigma)\mathrm{OPT}\), and attains the same factor with arbitrarily high polynomial confidence.

The formalization gives, for every fixed \(\varepsilon>0\), a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for metric \(k\)-median on finite rational metrics with specified candidate facilities. Every output is a nonempty subset of the candidate facilities and opens at most \(k\) of them.

Assuming \(P\ne NP\), it also proves that the infimum of all polynomial-time approximation factors in this model is exactly \(1+2/e\).

Comparator links

Result	Comparator statement
Randomized metric \(k\)-median approximation below two	KMedianRecovery.lean
Exact-budget recovery from accurate distinct cluster proxies	KMedianRefinedRecovery.lean
Exact approximation threshold under \(P\ne NP\)	KMedianThreshold.lean
Deterministic metric \(k\)-median approximation at the threshold	MetricKMedian.lean

Scope note on GitHub →