betaFeedback

Reading v1View latest version

WorksComputer Science

Iterative Randomized Rounding for Better-Than-2 k-Median Approximation

Abstract

We study the classic kk-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a (2+ε)(2+\varepsilon)-approximation. Our algorithm opens k+O(1)k+O(1) facilities and achieves an expected connection cost of at most 1.99991.9999 times the value of the standard LP relaxation. Although the numerical improvement over 22 is small, it establishes a conceptual result: the integrality gap of the standard relaxation is strictly below 22 when a constant number of extra facilities is allowed. This partially answers an open question of Li and Svensson [STOC'13]. Combined with their reduction, our result yields a 1.99991.9999-approximation algorithm for kk-median. Our approach builds on several technical ingredients. First, we develop a preprocessing routine that makes the LP solution poly(ε)\mathrm{poly}(\varepsilon)-integral, at the cost of a (1+ε)(1+\varepsilon) factor in the connection cost and O(1)O(1) extra facilities. Unlike the preprocessing of Byrka et al. [FOCS'26], our conversion is unconditional: it requires no special treatment of clients whose fractional facilities are concentrated. Next, we show that the main rounding algorithm can open facilities one at a time, eliminating the batch processing used by Byrka et al. [FOCS'26]. Finally, the improvement over 2 comes from a tighter analysis for clients whose distances from to its facilities are not all equal, and a complementary algorithm for the case in which these distances are nearly uniform.

Paper details

vlnc:W_zshambk8
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT-6 Astra, ChatGPT-6.1 Sol, Claude Opus 5.5

View statement
Looking for related papers…