Broader bidding rules improve guarantees for placing facilities
The method achieved a polynomial-time 1.95 approximation for facility location, improving on the long-standing factor of about 2.
Edited by Boris Djordjevic · Paperfoot
The preprint introduced broader bidding rules for facility location and proved an approximation guarantee with a factor of 1.95. Facility location balances the cost of opening facilities against the cost of connecting customers to them. The paper studied guarantees that preserve multipliers on opening costs, which are used to design algorithms for related clustering problems.
The method replaced the Greedy algorithm’s linear bidding rule with a richer family of rules. The authors proved that the resulting algorithm ran in polynomial time, meaning its computation scaled by a fixed power of the input size. The previous guarantee of this kind had stood at 2 for over two decades before a tiny improvement using local adjustments. The new approach modified the core algorithm itself.
Why it matters
The result improved a foundational tool for the k-median problem, which selects a set number of centers to minimize connection costs. When combined with a companion algorithm for stable inputs, the technique yielded a polynomial-time approximation factor below 2.
Caveats
The findings are mathematical proofs rather than empirical benchmarks on deployed systems. The work is a preprint that has not yet been peer-reviewed, and the full k-median guarantee relies on a separate companion paper.
In this paper
metric k-median problem
- Methods
- Generalized Greedy algorithm (Algorithm 1) (this paper)
- Links
- Code
Results
- Generalized Greedy algorithm (Algorithm 1), LMP approximation ratio, facility cost \hat{f}=1.9499\cdot f and the bidding function \beta(\alpha,d)=[\alpha-1.224\cdot d]^{+}: 1.9499
Algorithm 1 run with facility cost \hat{f}=1.9499\cdot f and the bidding function \beta(\alpha,d)=[\alpha-1.224\cdot d]^{+} is a 1.9499 -LMP approximation algorithm for UFL instances with facility cost f.
Theorem 4.3.
What it shows
- Algorithm 1 run with facility cost \hat{f}=1.9499\cdot f and the bidding function \beta(\alpha,d)=[\alpha-1.224\cdot d]^{+} is a 1.9499-LMP approximation algorithm for UFL instances with facility cost f.
Algorithm 1 run with facility cost \hat{f}=1.9499\cdot f and the bidding function \beta(\alpha,d)=[\alpha-1.224\cdot d]^{+} is a 1.9499 -LMP approximation algorithm for UFL instances with facility cost f.
Theorem 4.3.
- For values of \gamma\in[1,1.224], the factor-revealing program with \beta_{\gamma}(\alpha,d)=[\alpha-\gamma\cdot d]^{+} is upper-bounded by 2-(\gamma-1)^{2} for all n≥ 1.
For values of \gamma\in[1,1.224], the factor-revealing program from Definition 4.1 with \beta_{\gamma}(\alpha,d)=[\alpha-\gamma\cdot d]^{+} is upper-bounded by 2-(\gamma-1)^{2} for all n≥ 1.
Theorem 4.4.
- Algorithm 1 run with facility cost \hat{f}=\rho\cdot f is a \rho-LMP approximation algorithm for UFL instances with facility cost f when \rho upper bounds the factor-revealing program.
Then, Algorithm 1 run with facility cost \hat{f}=\rho\cdot f is a \rho -LMP approximation algorithm for UFL instances with facility cost f.
Theorem 4.2.
- The optimum value of the factor-revealing dual upper bounds the optimum value of the factor-revealing program for the bidding function \beta_{\gamma}(\alpha,d)=[\alpha-\gamma\cdot d]^{+}.
The optimum value of the factor-revealing dual in Definition 4.5 upper bounds the optimum value of the factor-revealing program in Definition 4.1 for the bidding function \beta_{\gamma}(\alpha,d)=[\alpha-\gamma\cdot d]^{+}.
Lemma 4.6.
- Smooth generalized bidding rules yield a polynomial-time 1.95-approximation that opens k+O_ε(log n) centers.
This yields a polynomial-time 1.95-approximation that opens k+O_ε(log n) centers.
Abstract
Quoted word for word from the full text on arXiv.
The paper
A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
arXiv, Oct 13, 2026, Open access, CC BY, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.18144
arXiv:2610.18144v1 in cs.DS
Cite as BibTeX
@misc{buhai2026betterthan2,
title = {A Better-than-2 Approximation for k-Median Part I: The Power of General Bids},
author = {Buhai, Rares-Darius and Cohen-Addad, Vincent and Fleischmann, Henry and Gupta, Anupam and Monforte, Antoni Jub'es and Pittu, Madhusudhan Reddy and Stouras, Miltiadis and Svensson, Ola and Vogl, Lukas},
year = {2026},
eprint = {2610.18144},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arxiv.2610.18144},
url = {https://arxiv.org/abs/2610.18144}
}