Ward's method yields a 2-approximation for k-means under well-separated optima (recovering the optimum under balance) in any dimension, with Ω((3/2)^d) lower bounds without separation and O(1) in 1D.
Greg Plaxton
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Analysis of Ward's Method
Ward's method yields a 2-approximation for k-means under well-separated optima (recovering the optimum under balance) in any dimension, with Ω((3/2)^d) lower bounds without separation and O(1) in 1D.