Metric k-median: approximation threshold and recovery

Source and verification

This article explains family 125 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Clients, facilities, and the exact budget

Metric $k$-median has a finite set $D$ of clients and a specified finite set $F$ of candidate facilities in a common metric space. Distances are rational and encoded in binary. For a nonempty $S\subseteq F$, define

$$\begin{array}{c}d(p,S)=\underset{s\in S}{\min }d(p,s),\\ \mathrm{cost}(S)=\sum _{p\in D}d(p,S),\\ {\mathrm{OPT}}_k=\underset{1\le |S|\le k}{\min }\mathrm{cost}(S).\end{array}$$

Clients and facilities may share locations, but their roles differ. In particular, the candidate set is supplied; it need not equal the client set. Assume $1\le k\le |F|$. Empty client sets have cost zero and are handled directly.

The budget is part of feasibility. Opening $k+1$ facilities can improve cost greatly, so a guarantee with extra facilities is not yet a $k$-median approximation. The two manuscripts develop different ways of returning to the exact budget.

🏷️ The threshold theorem and its endpoint

Deterministic threshold manuscript

For every fixed $\epsilon >0$, a deterministic algorithm returns $S\subseteq F$, $1\le |S|\le k$, with

$$\begin{array}{rl}& \mathrm{cost}(S)\\ & \le (1+2/e+\epsilon ){\mathrm{OPT}}_k.\end{array}$$

Its runtime is polynomial in the binary input length; the polynomial may depend on the fixed accuracy. (OpenAI, 2026)

The threshold value is approximately $1.736$. Together with the coverage hardness reduction below, the source concludes that, assuming $P\ne NP$, the infimum of deterministic polynomial-time approximation factors in this candidate-facility model is $1+2/e$. An infimum statement does not assert that the endpoint factor itself is attained.

The recovery companion separately gives a randomized approximation with factor $2-\sigma$ for some absolute $\sigma >0$, always respecting the budget. For any fixed $a>0$, its failure probability can be at most $(|D|+|F|+2{)}^{-a}$, and the algorithm can also satisfy the same factor in expectation. This is an independent construction, not a premise silently substituted for the sharper deterministic theorem. (OpenAI, 2026a)

🏷️ The coverage lower bound

Start with a universe of $m$ elements and a family of sets, of which at most $k$ may be selected. Represent elements by clients and sets by facilities. Give distinct points within either part distance two. A facility-client distance is one for incidence and three for nonincidence.

This is a metric. A same-part distance two is no greater than the sum of two cross-part distances, each at least one. A cross-part distance at most three is no greater than a same-part distance two plus a cross-part distance at least one. These checks cover every type of triangle.

If chosen facilities cover $c$ elements, their connection cost is exactly

$$c+3(m-c)=3m-2c.$$

A perfect cover has cost $m$. If every choice covers at most $(1-1/e+\delta )m$ elements, every solution has cost at least $(1+2/e-2\delta )m$. Applying the known perfect-completeness Max-$k$-Coverage gap gives hardness below $1+2/e$ for each fixed improvement, under $P\ne NP$. The manuscript imports that coverage gap; the elementary metric reduction above explains the resulting constant.

The construction uses separate client and candidate-facility sets. It does not establish the same lower bound under the additional restriction $F=D$, nor does ordinary deterministic NP-hardness alone rule out every randomized approximation model.

🏷️ Fractional openings and their rounding

The standard assignment LP has opening variables $y_i$ and client assignments $x_{ij}$, with

$$\begin{array}{c}\sum _i{x}_{ij}=1,0\le x_{ij}\le y_i\le 1,\\ \sum _i{y}_i\le k.\end{array}$$

It minimizes ${\sum }_{i,j}d(i,j)x_{ij}$ and lower-bounds ${\mathrm{OPT}}_k$. Assignment mass is not a shared service capacity: many clients may each assign up to $y_i$ to the same facility. Replacing these constraints by ${\sum }_j{x}_{ij}\le y_i$ would define a different problem.

The threshold manuscript first rounds openings to a constant grid $g=1/\Delta$, with even $\Delta$ depending only on accuracy. Separated representative clients determine disjoint bundles of opening mass. A bundle’s deficit is its shortfall from one unit; suppliers identify where its missing assignment mass resides. Rounding deficits together with suppliers limits both extra opening mass and the cost of restoring a full assigned unit.

The source bounds the opening-mass increase by $3g$ and makes the expected assignment-cost loss arbitrarily small. The coupled supplier argument must allow one facility to support many client assignments, in accordance with the uncapacitated LP.

🏷️ Surviving assignments and directed comparisons

Each positive grid opening becomes copies of mass $g$. A directed graph records which copies are erased when a source facility opens. Each target has exactly $\Delta$ incoming sources, sampled according to distance-dependent probabilities. Opening and erasure are balanced to control the number of selected facilities.

For each client, the analysis tracks surviving copies of its initially assigned unit and a persistent upper bound on its eventual connection distance. A potential combines remaining assignment cost with this bound; its coefficient depends on both elapsed time and surviving mass.

When one of the client’s own copies opens, the analysis continues to retain cheaper survivors. This produces a negative contribution that pays for losses caused by other erasures. A finite directed comparison inequality transfers positive row contributions to lower-distance rows whose negative contributions cover them. The source supplies rational polynomial certificates for its scalar estimates.

A source that would erase many copies is forced open. Since this event depends on the sampled graph, the potential change is first bounded for each realized graph, and only then averaged. Averaging under an unjustified graph-independent forcing probability would lose the stated drift guarantee. (OpenAI, 2026b)

🏷️ Derandomization and removal of surplus

Only selected low-order moments of each local choice enter the analysis. The source constructs polynomial-support rational distributions matching those moments. A constant number of rounds, fixed by accuracy, permits expansion of all relevant physical histories; the cheapest output satisfying the additive budget is retained.

This yields a deterministic approximation with at most $k+c$ facilities, where $c$ is an accuracy-dependent constant. The final step invokes the established Li–Svensson reduction removing constant additive surplus at an arbitrarily small extra approximation loss. The exact-budget theorem depends on this interface; the intermediate rounded solution alone is not its conclusion.

The rational encoding and the number of rounds matter for polynomial time. Preserving moments abstractly, without a finite support and bit-length bound, would not establish an implementable derandomization. No scalar-certificate program or clustering implementation was executed for this article.

🏷️ Recovery from a mostly accurate anchor

The companion begins with a supplied anchor $S$ of $h$ facilities and an unknown comparison solution $O$ of the same size and cost $P>0$. Assign clients to nearest comparison facilities, with fixed tie breaking. Write $C_i$ for the cluster of center $i$ and $P_i={\sum }_{p\in C_i}d(p,i)$.

Partition comparison centers into good and bad. Every good center has a distinct proxy ${\varphi }_i\in S$. If $P_g$ is the total good-cluster cost, the promise is

$$\sum _{i\mathrm{good}}\sum _{p\in C_i}d(p,{\varphi }_i)\le P_g+\mu P.$$

The algorithm receives the anchor and numerical parameters, not $O$, its cost, the partition, or the proxies. Local optimality is one way to produce a useful anchor, but is not part of the recovery promise itself.

Refined recovery statement

In the normalized model of disjoint indexed clients and facilities with positive integer distances bounded by a fixed polynomial in $N=|D|+|F|$, suppose the number of bad centers is at most $L_0\log N$. For fixed accuracy and sufficiently small fixed $\mu$, recovery always opens at most $h$ facilities and achieves factor $1+2/e+\epsilon$ relative to $P$ with probability at least $1-\zeta$, in time polynomial in $N$ and $\log (1/\zeta )$. (OpenAI, 2026a)

Single-exponential dependence on the exceptional count makes logarithmically many exceptions manageable:

$$e^{O(\log N)}=N^{O(1)}.$$

By comparison, $m^{O(m)}$ at $m=\Theta (\log N)$ can become $N^{O(\log \log N)}$. The distinction is therefore important even when both expressions might loosely be described as exponential parameter dependence.

The normalization is a genuine hypothesis. Accurate proxies in an arbitrary rational metric need not retain their promise after capping and rounding. The global application constructs anchors after normalization and separately transfers the final cost guarantee back.

🏷️ Sampling, removals, and submodular savings

Recovery samples clients in proportion to their distance from a reference set consisting of surviving anchor facilities and temporary leaf copies. A step either proposes a facility ball around a sampled client or removes its serving original facility. Population-radius estimates restrict the guesses.

Large radius-menu choices are charged to disjoint client sets and their comparison costs. This bounds the total probability loss of favorable adaptive histories by $\exp (-O(m))$, where $m$ is the number of bad centers, instead of paying separately for the entire metric range at every step. Saving all prefixes allows the algorithm to use a good stopping state without knowing the hidden comparison partition.

A subset dynamic program handles destinations without sampled balls. Choosing facilities within the other balls maximizes a monotone submodular saving, meaning the incremental saving decreases as more choices are already available. The $1-1/e$ gain from that optimization explains the appearance of $1+2/e$. Removing $m$ original facilities before adding at most $m$ real ones preserves the budget on every output. A refined two-stop analysis retains cost fractions needed for the sharper factor.

🏷️ Paying for openings and obtaining the global result

The second recovery ingredient fixes one final opening price $\lambda$, one set of copy lengths, and one actual replay of the opening process. All client budgets ${\alpha }_p$ belong to that same execution.

For a comparison cluster of cost $P_C$, the usual bound is ${\sum }_{p\in C}{\alpha }_p\le \lambda +2P_C$. At bounded price $\lambda \le T{P}_C$, the manuscript derives

$$\begin{array}{c}\sum _{p\in C}{\alpha }_p\le \lambda +(2-c(T)/2)P_C,\\ c(T)>0.\end{array}$$

The entire opening payment $\lambda$ remains available. Thus summing over clusters improves connection cost while still paying for all regular facilities. Mixing budgets from different prices or replays would not justify that sum.

The final argument considers nearby cardinality budgets. If reducing the budget changes optimum cost little, spare slots absorb a logarithmic surplus and strictness improves the cost below two. Otherwise, some nearby optimum is sensitive to deleting a center, giving separated clusters and only logarithmically many bad proxies. Recovery then applies. The algorithm generates candidates for both cases and selects the cheapest without being told the unknown optimum costs. A bounded-cost fallback supports both the high-probability and expectation guarantees on the original rational metric.

🏷️ Key steps and proof outlines

Exact moment compression makes derandomization finite

The threshold paper’s “Affine support reduction” starts with finitely many states $s_i$, rational weights ${\lambda }_i$ and feature vectors $v(s_i)\in {\mathbb{Q}}^d$. If more than $d+1$ states have positive weight, their augmented vectors $(1,v(s_i))$ have an affine dependence $z\ne 0$. Thus ${\sum }_i{z}_i=0$ and ${\sum }_i{z}_{i}v(s_i)=0$. Set

$$t=\underset{z_i>0}{\min }{\lambda }_i/z_i,{\lambda }_i^{\prime }={\lambda }_i-t{z}_i.$$

The weights remain nonnegative, total mass and feature expectations are unchanged, and at least one state disappears. Iteration leaves at most $d+1$ states. Clearing denominators and using minors produces dependencies of polynomial bit length; each elimination increases a common denominator’s bit length by only a polynomial amount. (OpenAI, 2026b)

The retained features include first moments and selected pair products of rounding variables. A pair update has opposite-signed coordinate changes, so the product of the changed coordinates is concave in the update parameter; its expectation does not increase. Products involving an untouched coordinate are affine and preserve expectation. Compression retains precisely the statistics needed by the variance and potential estimates.

It also preserves every statewise feasibility property because it only removes states and changes their weights. It does not preserve an arbitrary future adaptive law. The proof therefore specifies new features at each application and verifies the next estimate from those features. A constant number of physical rounds then permits enumeration of the compressed histories and selection of a cheapest feasible output.

Submodular savings explain the exponential constant

The recovery companion reduces its remaining facility choices to selecting at most one element from each of several parts, with a nonnegative monotone submodular gain $g$. Let $G(x)$ be expected gain when each part independently selects a categorical outcome according to fractional masses $x$. For an optimal feasible set $O$, diminishing returns gives

$$g(O)-G(x)\le \sum _{e\in O}{\partial }_{e}G(x)\le \sum _j\underset{e\in E_j}{\max }{\partial }_{e}G(x).$$

Thus selecting the largest derivative in every part points in a direction whose gain is at least the remaining optimality gap. Discretize into $T$ steps of size $1/T$. Fresh samples estimate derivatives; their bounded ranges permit a simultaneous error estimate even though the iterates are adaptive. A coupling of neighboring categorical laws bounds the finite-step error. The resulting recurrence has the form

$$G_{t+1}-G_t\ge \frac{g(O)-G_t-\eta g(O)}{T}.$$

Iterating from zero gives a gain approaching $(1-1/e)g(O)$ as the error budget decreases. Choosing dyadic $T$ makes the final categorical draw exact with bounded fair-bit use. This finite argument is the optimization ingredient producing the recovery factor; the geometric sampling lemmas establish that sufficiently valuable choices occur in its parts. (OpenAI, 2026a)

Recovery probability and exact cardinality are paid separately

The sampling proof charges large radius-menu choices to disjoint client groups. The total charge depends linearly on the number $m$ of bad centers, giving a favorable-prefix probability at least $\exp (-O(m))$. Repeating $\exp (O(m))$ times with a logarithmic confidence factor is polynomial when $m=O(\log N)$. Paying an independent metric-range factor at every step would instead introduce an unwanted $m\log m$ or larger exponent.

Every recovered candidate removes enough original facilities before adding the sampled replacements, so its budget is satisfied even on an unsuccessful random history. Accuracy is the probabilistic part. In the deterministic threshold route, intermediate candidates have a fixed additive surplus; the separate surplus-removal theorem pays the small extra cost needed to restore $k$. These are distinct budget arguments and neither follows merely from a low expected connection cost.

See Also

• Bin packing distinguishes additive resource allowances from multiplicative objective guarantees; here surplus facilities must be removed explicitly.
• Uniform sparsest cut provides another setting where a relaxation, a rounding algorithm, and a hardness reduction require separate arguments.

🏷️ Manuscripts and verification scope

• Single-exponential recovery and bounded-price strictness for metric $k$-median — pinned manuscript and companion source.
• The approximation threshold for metric $k$-median — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope distinguishes normalized anchor recovery, the randomized below-two application, the deterministic threshold approximation, and the infimum statement under P differing from NP. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Single-exponential recovery and bounded-price strictness for metric k-median.

🐻  OpenAI 2026b. The approximation threshold for metric k-median.