Name
Abstract | ||
|---|---|---|
The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e., n O(kd)) is, in general, exponential in the number of points (when kd=Ω(n/log n)). Recently Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006) showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to $2^{\varOmega (\sqrt{n})}$ with a construction in $d=\varOmega (\sqrt{n})$ dimensions. In Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006), they also conjectured the existence of super-polynomial lower bounds for any d≥2. Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2Ω(n). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00454-011-9340-1 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
k-means algorithm,n point,n o,simple construction,computational geometry,k cluster,super-polynomial lower bound,d-dimensional space,annual symposium,k-means requires exponentially,super-polynomial worst-case analysis,lower bound,k means,upper bound,k means algorithm,local search | Journal | 45 |
Issue | ISSN | Citations |
4 | 0179-5376 | 48 |
PageRank | References | Authors |
2.56 | 11 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Vattani | 1 | 171 | 11.45 |