arXiv · Oct 13, 2026
A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
By Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann et al.
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind the best k-median guarantees, for over two decades. Its 2-LMP guarantee was only recently broken by a small amount ((2-η)-LMP where η ≈ 2.25 · 10⁻⁷) through local-search post-processing. That analysis relies on the structure of worst-case instances, and it appears difficult to obtain substantial further improvements along those lines. We take a different approach and change the algorithm itself: we introduce general bidding functions, replacing the classical linear bid with a richer family of rules and prove a polynomial-time 1.95-LMP approximation, a large improvement over the long-standing factor of~2. We further show that these generalized bidding rules can be made smooth (log-adaptive), building on the recent framework developed for the classical Greedy algorithm by Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson. This yields a polynomial-time 1.95-approximation that opens k+O_ε(log n) centers. Combined with a (1.89+ε)-approximation algorithm for stable instances in our companion work cite{stableinstances}, we achieve a better-than-2 approximation for the k-median problem in polynomial-time.