The metric k-median approximation threshold and recovery

What OpenAI claims

Gives a deterministic polynomial-time (1+2/e+ε)-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming P ≠ NP, the optimal infimum approximation factor is 1+2/e. (Lean)

Papers (2)

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

   24 September 2026 · Preprint, not peer reviewed · PDF

   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+ε) 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-σ) 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.

2. The approximation threshold for metric k-median

   24 September 2026 · Preprint, not peer reviewed · PDF

   For every fixed ε > 0, we give a deterministic polynomial-time (1+2/e+ε)-approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under P ≠ NP, the infimum approximation factor in this model is therefore 1+2/e.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.