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. (Lean)

Manuscripts (2)

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

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-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.

The approximation threshold for metric k-median

September 24, 2026 · source · cite as \cite{OAI:The-Approximation-Threshold-for-Metric-k-Median-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.

Result 125 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.