arXiv preprint ·
Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the classic $k$-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsilon)$-approximation. Our algorithm opens $k+O(1)$ facilities and achieves an expected connection cost of at most $1.9999$ times the value of the standard LP relaxation. Although the numerical improvement over $2$ is small, it establishes a conceptual result: the integrality gap of the standard relaxation is strictly below $2$ 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.9999$-approximation algorithm for $k$-median. Our approach builds on several technical ingredients. First, we develop a preprocessing routine that makes the LP solution $\mathrm{poly}(\varepsilon)$-integral, at the cost of a $(1+\varepsilon)$ factor in the connection cost and $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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Beyond 3SUM-Hardness for Geometric Problems
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
The Exact Robustness of Smith's Rule with Predicted Processing Times
Near-Quadratic Time Multivariate Polynomial Interpolation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.