A 1.224 slope in the greedy bid cuts k-median's approximation to 1.95

A Better-than-2 Approximation for k-Median Part I: The Power of General Bids

Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte, Madhusudhan Reddy Pittu, Miltiadis Stouras, Ola Svensson, Lukas Vogl

cs.DS

2026-10-13

Bidding [α−1.224d]+ is 1.9499-LMP for facility location. With log-adaptive smoothing and a stable-instance routine, k-median gets a polynomial-time 1.95-approximation.

What problem this solves

Metric k-median picks k centers so that the sum of distances from n clients to the nearest center is minimized, with distances obeying the triangle inequality. The hardness threshold is 1+2/e. Polynomial-time algorithms stayed near 2 for more than twenty years. The stall sits in the Jain-Vazirani Lagrangian reduction.

The cardinality constraint is written as a uniform opening cost f. Binary search on f returns one facility-location solution with fewer than k centers and one with more. A convex combination opens k centers in expectation. The reduction needs an LMP guarantee: after opening costs are paid in full, connection cost is at most α times (optimal facility-location cost minus opening cost). The classical greedy bid [α−d]+ is 2-LMP. Bi-point rounding multiplies by another 2, so k-median only reached 4.

Later algorithms were allowed to open k+O(1) centers. Improved bi-point rounding, stacked on a local-search post-processing that beats 2 by only η≈2.25×10^{-7}, reached 2.613. A log-adaptive greedy and iterative rounding of the standard LP both reached 2+ε. Opening k centers in expectation and opening at most k centers met at 2. Plain facility location already has a 1.488-approximation, but that guarantee is not LMP and does not plug into the reduction.

Method

The greedy loop stays the same. Active clients share a rising budget α. A facility opens when the bids cover its opening cost, and a client freezes once α can pay the distance to an open facility. The bid is what changes. Classically the client offers the entire residual after subtracting distance. This paper uses β(α,d)=[α−γd]+ with γ=1.224, so distance is inflated before it is subtracted and far facilities receive less.

A legal bid never exceeds the residual budget. It is monotone, scale-equivariant, and superadditive. Superadditivity is the accounting rule. A client's true cost is the bid paid when it is first served, plus a bid at every later move to a closer facility, plus the final connection distance. Linear bids telescope, so cost equals the frozen α. For γ>1 the telescope breaks. Charging α instead of true cost lets the instance in Figure 3 push the ratio back to 2.

The old tight example parks n−1 clients on the expensive facility and leaves one client at distance 1 from both facilities, which are distance 2 apart. A linear bid lets that isolated client fund the cheap facility alone, the ratio tends to 2, and greedy can open the cheap facility first. For γ>1 that bid is too small and the ratio on the example falls to at most γ. Retuned, the example is tight for every γ in (1, 1.224], at 2−(1−γ)^2−1/n. At γ=1.224 the value is at most 1.9499.

Theorem 4.4 shows that on γ in [1, 1.224] the factor-revealing program is at most 2−(γ−1)^2 for every n, matching the construction. Running the greedy with opening costs scaled by 1.9499 is a 1.9499-LMP algorithm for the original costs. The program is no longer one LP. A binary variable flags whether each bid is positive, producing a family of 2^{Θ(n²)} linear programs. The dual solution adapts to the first time a client bids a positive amount, and continuity plus the intermediate-value theorem supplies feasible advice.

Bi-point rounding cannot beat (1+2/e)√φ≈2.208, so the paper switches to a log-adaptive schedule. Time θ grows by factors of 1+ε² and distances are scaled by 1−δ. When opening the second kind of facility, only clients within distance εθ may push their budgets above the current θ. The two opening rules use different distance scalings, so two facilities that are candidates at the same moment lie at distance ≤δθ or ≥θ/γ. If the program is at most ρ and ρ≥1.01γ, the smooth algorithm is (1+2δ)ρ-LMP. Absorbing the loss into ε gives Theorem 1.2: at most k+O(log n/ε²) centers at cost (1.9499+ε)·opt.

Exactly k centers in polynomial time needs the companion paper. If the extra centers barely increase the optimum, the pseudo-solution is already good. Otherwise some intermediate size is β-stable: dropping one more center multiplies the optimum by at least 1+β. On those instances the companion returns cost (1.89+O(ε))·opt with probability 1−ε, for ε below 1/200. The two halves are Theorem 1.1, a randomized polynomial-time 1.95-approximation.

Remark 1.5 replaces the single slope by a convex combination of 13 bids, coefficients Ws/10^8, slopes from 137/125 to 41/20, and gets an LMP ratio of 1.844. The same remark shows that every legal bid leaves this factor-revealing program at least 1.8. Both claims are Lean certificates produced by GPT-6 Astra. The paper states that the other proofs were written by the authors. GPT-5.6 Sol and GPT-6 Astra checked proofs and edited prose, and the Lean certificate for Theorem 4.4 is also from GPT-6 Astra.

Results

MethodMeasureResult
Linear-bid greedyLMP / k-median2 / 4
Local-search post-processingLMP2−η, η≈2.25×10^{-7}
That improvement plus refined bi-point roundingk-median2.613
Log-adaptive greedy; LP iterative roundingk-median2+ε
γ=1.224LMP1.9499
Log-adaptive versionCenters and cost≤k+O(log n/ε²) at (1.9499+ε)·opt
Companion, stable instancesExactly k centers(1.89+O(ε))·opt, probability 1−ε
The two papers togetherPolynomial-time k-median1.95
Mixture of 13 bidsLMP1.844
Any legal bidProgram lower bound1.8
Hardnessk-median1+2/e
LMP bi-point roundingKnown threshold(1+2/e)√φ≈2.208

The stated 1.9499 is an upper bound on 2−(1.224−1)^2. For every γ in (1, 1.224], the quantity 2−(1−γ)^2 is tight against the construction in Figure 2.

Why it matters

The previous LMP improvement was 2.25×10^{-7}. The same style of greedy now reaches 1.9499, about 0.05 below 2. The factor 2 was tied to the tight examples of the linear bid.

Smoothing is a black box. A better legal bid can reuse the guarantee that opens O(log n/ε²) extra centers, without a new smoothness proof. The 1.844 mixture is a step in that direction. Its evidence is a Lean certificate.

Algorithm 1 only changes the bid. The 1.95 guarantee calls the stable-instance subroutine and picks up an exp(O(1/β)) factor in the runtime. The approximation ratio moves forward. This is not a faster clustering routine.

The paper records two concurrent routes. On 6 October 2026, OpenAI announced two better-than-2 results, one of which pushes iterative rounding to 1+2/e+ε. Byrka, Yuhao Guo, Yang Hu, Shi Li, and coauthors independently obtained 2−σ for a small constant σ. Those are an announcement and a personal communication. If the 1+2/e+ε claim holds, 1.95 is not the best k-median factor. The 1.9499-LMP bound is still this paper's own bidding analysis.

Limitations

The one-slope proof stops at γ=1.224 because that is where the upper bound meets the tight example, not because a wider search found an optimal slope. The paper gives no upper bound past that point.

1.8 is a floor for this factor-revealing program. Changing the bid does not fill the gap from 1.8 down to the hardness threshold 1+2/e.

The 1.95 result spans two papers. This one contributes 1.9499-LMP and the (1.9499+ε) guarantee with k+O(log n/ε²) centers. Exact k centers depend on the companion, and the stable-instance proof is not checked here.

Log-adaptivity pays a (1+2δ) factor and needs ρ≥1.01γ, with δ small relative to 1/γ and ε small relative to δ. An arbitrarily small ε absorbs the loss and makes the polynomial degree large. There are no experiments, and no count of extra centers at a concrete n.

The 1.844 ratio and the 1.8 floor sit in a remark, on a different footing from the handwritten 1.9499 proof. The concurrent 1+2/e+ε claim is only an announcement. This paper does not contain that proof.

Terms

Source

What people are saying

Related papers

All paper explainers