betaFeedback

WorksComputer Science

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

Abstract

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+φ)(1+H_{k-1}), where φ≈1.618φ\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.

Paper details

vlnc:W_6msjrm43
Version
v1 · latest
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

Not recorded for this paper

View statement
Looking for related papers…