← 研踪 PaperTrailarXiv:2610.31229 · v2
Iterative Randomized Rounding for $k$-Median in General and Euclidean Metrics
首次提交 2026-10-22 21:13
版本更新 2026-11-05 21:30
雷达观测 2026-11-06 12:09
摘要
We refine the iterative rounding framework of Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which gives a $(2+\varepsilon)$-approximation for $k$-median. Our algorithm opens $k+O(1)$ facilities with expected connection cost at most $1.9999$ times the standard LP value. Despite the small numerical gain, this shows that the LP integrality gap is below $2$ with a constant additive facility allowance, partially answering Li and Svensson's open question [SICOMP'16]. Their reduction yields a $1.9999$-approximation opening at most $k$ facilities. Our preprocessing makes the LP solution $\mathrm{poly}(\varepsilon)$-integral with a $(1+\varepsilon)$ loss in each client's expected connection cost and $O(1)$ extra facilities, without special treatment of clients with concentrated fractional facilities. We replace batch processing with single-facility openings and combine a tighter analysis for clients with unequal distances to their facilities with a complementary algorithm for nearly uniform distances. In Euclidean metrics, we obtain a $1.71955$-approximation for $k$-median and a $1.4561$-approximation for uncapacitated facility location (UFL). For every $p\ge2$ and sufficiently small $\varepsilon>0$, we obtain a $((3^p+2)/3+\varepsilon)$-approximation for $k$-clustering with $p$-th power distance costs. For $p=2$, our $(11/3+\varepsilon)$-approximation for $k$-means improves the $(3+\ln2+\varepsilon)$ bound of Anand, Charikar, Cohen-Addad, Gao, Grandoni, Lee, Sharma, and van Wijland [SODA'27]. The Euclidean $k$-median, $k$-means, and UFL ratios are below the respective general-metric hardness bounds $1+2/e$, $1+8/e$ [STOC'02], and $1.463$ [J. Algorithms'99]. The Euclidean $k$-median bound relies on a geometric inequality proved via a nonnegativity certificate constructed from positive-semidefinite kernels.
作者备注：76 pages, 1 figure. The abstract was abridged to meet the arXiv requirement
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 21:30 · 最新观测版本
Iterative Randomized Rounding for $k$-Median in General and Euclidean Metrics
We refine the iterative rounding framework of Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which gives a $(2+\varepsilon)$-approximation for $k$-median. Our algorithm opens $k+O(1)$ facilities with expected connection cost at most $1.9999$ times the standard LP value. Despite the small numerical gain, this shows that the LP integrality gap is below $2$ with a constant additive facility allowance, partially answering Li and Svensson's open question [SICOMP'16]. Their reduction yields a $1.9999$-approximation opening at most $k$ facilities. Our preprocessing makes the LP solution $\mathrm{poly}(\varepsilon)$-integral with a $(1+\varepsilon)$ loss in each client's expected connection cost and $O(1)$ extra facilities, without special treatment of clients with concentrated fractional facilities. We replace batch processing with single-facility openings and combine a tighter analysis for clients with unequal distances to their facilities with a complementary algorithm for nearly uniform distances. In Euclidean metrics, we obtain a $1.71955$-approximation for $k$-median and a $1.4561$-approximation for uncapacitated facility location (UFL). For every $p\ge2$ and sufficiently small $\varepsilon>0$, we obtain a $((3^p+2)/3+\varepsilon)$-approximation for $k$-clustering with $p$-th power distance costs. For $p=2$, our $(11/3+\varepsilon)$-approximation for $k$-means improves the $(3+\ln2+\varepsilon)$ bound of Anand, Charikar, Cohen-Addad, Gao, Grandoni, Lee, Sharma, and van Wijland [SODA'27]. The Euclidean $k$-median, $k$-means, and UFL ratios are below the respective general-metric hardness bounds $1+2/e$, $1+8/e$ [STOC'02], and $1.463$ [J. Algorithms'99]. The Euclidean $k$-median bound relies on a geometric inequality proved via a nonnegativity certificate constructed from positive-semidefinite kernels.
查看此版本解读 →查看此版本原文 ↗