1 · The essentials
Imagine choosing at most service locations from an allowed list, so that the total distance people must travel is as small as possible. This is the location-choice problem studied by these manuscripts. They seek efficient methods whose total travel distance stays within a guaranteed multiple of the best possible value. The companion manuscript claims a method with a guarantee of for any fixed positive allowance . It also claims that, assuming , the best achievable limiting guarantee is . The main manuscript develops a way to repair a supplied selection of locations while respecting the limit on how many may open. It reports both a strong guarantee under additional conditions and a more general randomized guarantee strictly below twice the best cost. The main result has a Lean formalization; the companion manuscript’s threshold claim is a separate result.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine repairing a delivery company’s proposed depot list rather than planning everything from scratch. The recovery argument is especially effective when only a few groups lack good, separate stand-ins in that list, and the repaired list must still respect the depot limit. This image does not capture the precise distance and error conditions required by the result.
Why it matters
The family connects two questions: how to recover a good solution from a supplied starting point, and how close an efficient algorithm can get to the best possible cost. The facility budget is part of the guarantee, not something relaxed to obtain a better distance bound. The companion manuscript claims a limiting approximation factor that is optimal under .
2 · Going further
Metric -median asks for at most facilities, chosen from specified candidates, minimizing the sum of distances from clients to their nearest selected facility. The threshold statement concerns finite rational metrics and polynomial-time algorithms. An approximation factor means that the returned cost is at most times the optimal cost. Manuscript 2 claims a deterministic polynomial-time -approximation for every fixed , and identifies as the infimum approximation factor under .
Manuscript 1 focuses on exact-budget recovery from a supplied anchor solution. Its running-time dependence is single-exponential in the number of comparison clusters without accurate, distinct proxies in that anchor. On positive integral metrics of polynomially bounded diameter, sufficiently small total proxy error and logarithmically many such clusters give a polynomial-time approximation with arbitrarily high success probability. Thus, the recovery guarantee depends on both the quality of the proxies and the number of clusters not adequately represented.
The main abstract also reports bounded-price strictness for one compatible execution of a logarithmic-surplus construction. It says that combining recovery and payment arguments yields a randomized approximation for an absolute on arbitrary finite rational metrics, both with high probability and in expectation. Every output opens at most facilities. The supplied abstract does not detail the payment mechanism or the construction.
The companion manuscript states the broader deterministic threshold result without the proxy conditions of the conditional recovery guarantee. The source does not explain its full derivation from the recovery machinery. The main result has a Lean formalization, but the supplied description does not specify which subsidiary claims it covers; it does not identify Manuscript 2 as formalized.
Useful notions
- Distances satisfying the triangle inequality
- Minimizing total assignment distance
- Approximation factors
- Polynomial-time algorithms
- Randomized guarantees and expectation
What was known before / what is new
Before
The source supplies no historical account of earlier approximation guarantees or recovery methods. It presents as the assumption behind the claimed optimality of the limiting factor, but gives no details of the underlying lower-bound argument.
New
The main manuscript introduces exact-budget recovery with single-exponential dependence on the number of comparison clusters lacking accurate, distinct proxies, together with a bounded-price strictness result. Its abstract reports that recovery and payment arguments yield a randomized approximation strictly below on arbitrary finite rational metrics. The companion manuscript claims the deterministic guarantee and the corresponding conditional infimum threshold.
Limits and assumptions
The near-threshold recovery guarantee requires positive integral distances, polynomially bounded diameter, sufficiently small total proxy error, and only logarithmically many comparison clusters lacking accurate, distinct proxies. The broader randomized guarantee has factor , not the companion’s near-threshold factor, and its strictness argument concerns one compatible execution of the specified construction. The companion’s deterministic claim applies to finite rational metrics with specified candidate facilities and each fixed positive ; an infimum statement does not itself assert an algorithm attaining exactly . Threshold optimality is conditional on . The main result has a Lean formalization, whose detailed scope is not provided here; the companion result is not identified as formalized. The source lists no further open problems.
Mini glossary
- Metric k-median —
- The problem of choosing at most allowed facilities to minimize total distance from clients to their nearest chosen facility in a metric.
- Approximation factor —
- A guaranteed upper bound on the returned solution’s cost as a multiple of the optimal cost.
- Anchor solution —
- The supplied starting solution whose proxies are used in the main manuscript’s recovery procedure.
- Exact-budget recovery —
- Recovery of a solution while respecting the limit of at most open facilities.
- Infimum approximation factor —
- The limiting lower value of achievable approximation guarantees, which need not itself be attained.
- Lean formalization —
- A representation of a mathematical result and its proof checked in the Lean proof assistant.
Keywords : Metric k-median · Approximation threshold · Exact-budget recovery
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives a deterministic polynomial-time -approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming , the optimal infimum approximation factor is .
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Single-exponential recovery and bounded-price strictness for metric k-median
24/09/2026We 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 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 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
24/09/2026For every fixed ε > 0, we give a deterministic polynomial-time -approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under , the infimum approximation factor in this model is therefore .