Metric k-median: approaching the sharp approximation threshold

← All digests

Family 125 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

A city wants to open at most $k$ service centers. Residents use their nearest open center, and the objective is to minimize the total travel distance. Candidate sites are fixed in advance. How close can an efficient algorithm come to the best possible placement?

This is metric $k$-median, a basic clustering and facility-location problem. The word “metric” means that distances satisfy the triangle inequality; the locations need not lie in a Euclidean plane. The model includes networks and many other finite distance spaces.

Exact optimization is computationally difficult, so the central question asks for an approximation guarantee. If the optimum cost is $\mathrm{OPT}$, an $\alpha$-approximation always returns cost at most $\alpha\mathrm{OPT}$. A smaller factor is better.

Opening a few extra facilities can greatly simplify the problem. The real challenge is obtaining a good cost while respecting the budget of $k$ on every output. This family contains two approaches to that challenge. Its strongest claim reaches every fixed factor above $1+2/e$, approximately 1.736, matching the known hardness boundary in the specified candidate-facility model.

2. Background and essential definitions

Let $J$ be the finite client set, $F$ the finite set of allowed facilities, and $d$ the metric on their locations. The two sets are specified separately; the problem does not require $F=J$. For a nonempty chosen set $S\subseteq F$, define

$$d(j,S)=\min_{i\in S}d(j,i), \qquad \operatorname{cost}(S)=\sum_{j\in J}d(j,S).$$

The optimum is the minimum of this cost over $1\le |S|\le k$. Distances are rational numbers encoded in binary, so their precision contributes to input size. Empty client sets can be handled immediately with cost zero.

A fractional relaxation allows a facility to be partly open. Let $y_i\in[0,1]$ describe its opening amount, and let $x_{ij}$ be the fraction of client $j$‘s assignment sent there. Standard constraints are

$$\sum_i x_{ij}=1,\qquad x_{ij}\le y_i, \qquad \sum_i y_i\le k.$$

The objective is $\sum_{i,j}d(j,i)x_{ij}$. Every actual solution gives a feasible fractional solution, so the fractional optimum is a lower bound on the true optimum. Rounding means converting fractional openings into actual facilities while controlling the cost increase.

Assignment fractions do not impose service capacities: one open facility can serve many clients. This distinction matters when several clients share the same fractional supplier.

A pseudo-approximation permits a constant additive number of extra facilities, returning at most $k+c$. It is an intermediate tool, not a feasible answer to the original budget-constrained problem. The manuscripts must eventually remove those extra facilities.

3. Development history and previous partial results

Metric $k$-median helped shape several central techniques in approximation algorithms. Charikar, Guha, Tardos, and Shmoys obtained a constant-factor guarantee through linear-programming rounding. Jain and Vazirani connected the problem with facility location through opening prices and primal-dual methods. Bounded-swap local search supplied a different route, with the classical $3+\varepsilon$ guarantee of Arya and coauthors.

An opening price penalizes each facility, but a price constraint is not the same as an exact cardinality constraint. Li and Svensson’s pseudo-approximation reduction made this gap more manageable: a constant additive surplus can be removed at an arbitrarily small extra approximation loss, with an accuracy-dependent computational overhead.

Subsequent rounding improvements brought the factor through values above two. Cohen-Addad and coauthors reached $2+\varepsilon$, announced in 2025, through a construction combining a logarithmic surplus of facilities with recovery arguments. Their full manuscript is a direct predecessor of M1. A later iterative graph-rounding framework is the main structural predecessor of M2.

On the hardness side, maximum-coverage gaps yield the threshold $1+2/e$ for the general candidate-facility model. The distinction between separately specified facilities and the restriction $F=J$ is discussed by Anand and Lee. M2 uses that existing hardness result to interpret its algorithmic claim as a threshold theorem; it does not present a new hardness reduction as the principal advance.

4. What the new manuscripts claim

A deterministic algorithm near the hardness boundary

M2 states that, for every fixed $\varepsilon>0$, a deterministic polynomial-time algorithm returns a set $S\subseteq F$ satisfying

$$|S|\le k, \qquad \operatorname{cost}(S)\le \left(1+\frac2e+\varepsilon\right)\mathrm{OPT}.$$

Polynomial time refers to the full binary encoding length of the finite rational metric. The polynomial may depend on $\varepsilon$. This is not a claim of a single running-time bound polynomial jointly in input size and $1/\varepsilon$.

Combined with the known hardness under $\mathrm P\ne\mathrm{NP}$, the claim makes $1+2/e$ the infimum of deterministic polynomial-time approximation factors in this model. An infimum need not be attained: algorithms for every factor strictly above the boundary do not automatically give an algorithm at the boundary itself.

Recovery from a nearly adequate anchor

M1 develops a different tool. An anchor is an already supplied facility set of the required size. Imagine an unknown comparison solution whose client clusters mostly have accurate, distinct representatives in that anchor. A small exceptional set of clusters lacks such representatives.

Under a precise total proxy-error promise, positive integral distances of polynomially bounded diameter, and at most $L_0\log N$ exceptional clusters, M1 claims recovery with factor $1+2/e+\varepsilon$ in polynomial time. Here $N=|J|+|F|$, and the accuracy parameters and $L_0$ are fixed. The algorithm is given the anchor, but not the comparison solution, the good/bad partition, or its proxy map.

The dependence on the number of exceptional clusters is single-exponential, which makes logarithmically many exceptions affordable. The promise does not require the anchor itself to be locally optimal.

M1 also combines recovery with payment accounting to claim an independent randomized $(2-\sigma)$-approximation for an absolute $\sigma>0$ on arbitrary finite rational metrics. It respects $k$ on every output and gives both high-probability and expected-cost guarantees. This general-metric consequence has a weaker factor than M2, but arises from a different argument.

5. Why the advance matters

Provisional importance: 4/5. The strongest claim closes a major approximation gap for a foundational clustering problem. Matching an algorithmic upper bound to a conditional hardness boundary identifies how much loss efficient computation must tolerate, up to the endpoint issue.

The exact facility budget makes the result more substantial than a cost guarantee obtained by opening extra centers. In applications, a cardinality constraint can represent a genuine limit on facilities, equipment, or representatives. The mathematical theorem treats that constraint directly in its final output.

The companion recovery result also isolates a potentially useful principle: an anchor may be enough when only a few comparison clusters are poorly represented. Its running-time dependence distinguishes a truly single-exponential parameter cost from bounds such as $k^{O(k)}$, which need not become polynomial when $k$ grows logarithmically.

The rating concerns theoretical significance. Neither manuscript establishes small constants or competitive performance on practical clustering datasets, and the threshold should not be transferred without qualification to Euclidean metrics or other restricted models.

6. The main idea

Round while retaining useful assignments

M2 begins with the fractional solution and places opening amounts on a fixed grid. The grid spacing depends on accuracy but not on the number of clients or the metric’s bit length. Nearby representative clients define bundles of opening mass; deficits are rounded together with the facilities that supply them.

An iterative directed graph then coordinates openings and erasures of fractional copies. Opening one facility can remove several competing copies, gradually turning fractional mass into actual choices. The analysis balances these actions so that the final number of openings exceeds $k$ by only an accuracy-dependent constant.

The cost argument tracks more than the first facility that becomes available to a client. Some cheaper surviving assignments remain useful even after an opening. A potential function records both their remaining cost and a bound on the client’s eventual connection distance. Keeping this information creates a compensating decrease that pays for harmful erasures elsewhere.

This is the claimed source of the improvement below two within the graph framework. A directed comparison inequality controls the average change of the potential. Cases in which one opening erases many copies require separate treatment before averaging, because the decision to force an opening depends on the realized graph.

The analysis initially uses randomness. M2 then replaces local choice distributions by polynomial-size rational distributions preserving the moments actually used in the estimates. Since the number of rounds depends only on accuracy, it can enumerate the relevant histories and choose the best eligible outcome. Finally, the Li–Svensson reduction removes the constant additive surplus. Both derandomization and budget repair are necessary parts of the final theorem.

Repair an anchor without losing the budget

M1 samples clients in proportion to how poorly the current reference facilities serve them. It alternates guesses about missing cluster locations with removals of existing facilities. Temporary leaf copies organize possible replacements without pretending those copies are legitimate final sites.

A favorable sequence of sampling decisions identifies enough of the exceptional structure. The manuscript charges difficult radius guesses to disjoint client groups, limiting the total probability loss to an exponential in the exceptional count. A subset dynamic program handles some replacement choices; a submodular savings problem handles the others. Submodularity means that the marginal benefit of an extra choice decreases as more choices have already been made.

The completion step removes as many original facilities as it adds replacements. Separately, payment inequalities retain enough budget to pay for every opening while improving connection costs. The manuscript attributes bounded-price strictness to earlier work; its contribution here is a self-contained argument compatible with the particular execution and its recovery procedure.

7. Scope, limitations, and open questions

The threshold is for arbitrary finite rational metrics with a separately specified candidate set. Restricting candidate centers to the clients changes the hardness question. Specialized geometric metrics may allow stronger guarantees and require separate analysis.

M1’s refined recovery theorem has a normalized integral-distance promise. The paper does not assert that an arbitrary promised anchor keeps that promise after capping and rounding distances. Its general-metric application constructs and analyzes anchors after normalization, then transfers the final result back.

M2’s approximation factors approach $1+2/e$ but do not claim the exact endpoint. The constants, grid sizes, and number of rounds can depend heavily on accuracy. Practical implementation and a favorable dependence on $\varepsilon$ remain separate issues.

Finally, the intermediate comparison with the fractional objective includes extra facilities. It should not be read as a direct exact-budget rounding theorem with the same bound for the original relaxation. The surplus-removal reduction is part of the stated route to the final guarantee.

8. Sources and further reading

The linked historical papers explain fractional rounding, local search, pseudo-approximations, and the model-dependent hardness boundary. M1 below supplies the anchor recovery and payment approach; M2 supplies the deterministic threshold claim. They belong to one family but provide distinct algorithms and should not be merged into an unstated common guarantee.

Source manuscripts

• M1. OpenAI, Single-exponential recovery and bounded-price strictness for metric k-median (2026).
• M2. OpenAI, The approximation threshold for metric k-median (2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.