跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.18544 · v1

Tight Bounds for k-Median++ and Improved Bounds for k-Means++

首次提交 2026-11-14 02:50
版本更新 2026-11-14 02:50
雷达观测 2026-11-16 13:44
arXiv ↗PDF ↗

摘要

The popular kk-means++ algorithm, or DℓD^\ell-sampling, is a fundamental primitive in both the theory and practice of clustering. In the bi-criteria setting, the algorithm samples k+Δk+Δ centers (Δ≥0Δ\ge0), and its cost is compared with the optimum using kk centers. Despite extensive study over the past two decades, its exact approximation ratio and tight bi-criteria guarantees remain unknown. We give a unified analysis for every distance exponent ℓ>0\ell>0, every k≥1k\ge1, and every Δ≥0Δ\ge0. For metric kk-median, our bounds are tight for all kk and ΔΔ. Without extra centers, the exact approximation ratio is 2(1+Hk−1)2(1+H_{k-1}) (also in Euclidean space), improving the previous upper bound by a factor of 22 (HjH_j denotes the jjth harmonic number). This tight analysis reveals that even one extra center improves the approximation ratio by an additive Θ(log⁡log⁡k)Θ(\log\log k), whereas previous bounds show no improvement. For every ℓ>0\ell>0, our analysis gives upper bounds with the same dependence on kk and ΔΔ as our tight bound for metric kk-median, with leading constants depending only on ℓ\ell and whether the metric is Euclidean. Beyond the improved dependence on ΔΔ, our leading constants are smaller than those in previous analyses. In particular, for the widely used Euclidean kk-means objective, our upper bound without extra centers is (1+φ)(1+Hk−1)(1+\varphi)(1+H_{k-1}), where φ≈1.618\varphi\approx1.618 is the golden ratio, improving upon the previous constant of 55. With oversampling, a constant fraction of extra centers is known to provide a constant-factor approximation. For example, with 10%10\% extra centers, our guarantee is 5.75.7, compared with the best previous guarantee of 25.925.9.

作者备注:46 pages, 2 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-14 02:50 · 最新观测版本

Tight Bounds for k-Median++ and Improved Bounds for k-Means++

The popular kk-means++ algorithm, or DℓD^\ell-sampling, is a fundamental primitive in both the theory and practice of clustering. In the bi-criteria setting, the algorithm samples k+Δk+Δ centers (Δ≥0Δ\ge0), and its cost is compared with the optimum using kk centers. Despite extensive study over the past two decades, its exact approximation ratio and tight bi-criteria guarantees remain unknown. We give a unified analysis for every distance exponent ℓ>0\ell>0, every k≥1k\ge1, and every Δ≥0Δ\ge0. For metric kk-median, our bounds are tight for all kk and ΔΔ. Without extra centers, the exact approximation ratio is 2(1+Hk−1)2(1+H_{k-1}) (also in Euclidean space), improving the previous upper bound by a factor of 22 (HjH_j denotes the jjth harmonic number). This tight analysis reveals that even one extra center improves the approximation ratio by an additive Θ(log⁡log⁡k)Θ(\log\log k), whereas previous bounds show no improvement. For every ℓ>0\ell>0, our analysis gives upper bounds with the same dependence on kk and ΔΔ as our tight bound for metric kk-median, with leading constants depending only on ℓ\ell and whether the metric is Euclidean. Beyond the improved dependence on ΔΔ, our leading constants are smaller than those in previous analyses. In particular, for the widely used Euclidean kk-means objective, our upper bound without extra centers is (1+φ)(1+Hk−1)(1+\varphi)(1+H_{k-1}), where φ≈1.618\varphi\approx1.618 is the golden ratio, improving upon the previous constant of 55. With oversampling, a constant fraction of extra centers is known to provide a constant-factor approximation. For example, with 10%10\% extra centers, our guarantee is 5.75.7, compared with the best previous guarantee of 25.925.9.

查看此版本解读 →查看此版本原文 ↗