k-means requires exponentially many iterations even in the plane
| dc.creator | Vattani, Andrea | |
| dc.date | 2008-12-01 | |
| dc.date.accessioned | 2026-07-07T12:08:33Z | |
| dc.date.available | 2026-07-07T12:08:33Z | |
| dc.description | 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. O(n^{kd})) can be exponential in the number of points. Recently, Arthur and Vassilvitskii [3] showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to 2^{Ω(\sqrt{n})} with a construction in d=Ω(\sqrt{n}) dimensions. In [3] they also conjectured the existence of superpolynomial 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)}. | |
| dc.description | Submitted to SoCG 2009 | |
| dc.identifier | https://arxiv.org/abs/0812.0382 | |
| dc.identifier | http://arxiv.org/abs/0812.0382 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/209358 | |
| dc.subject | Computational Geometry | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Machine Learning | |
| dc.title | k-means requires exponentially many iterations even in the plane | |
| dc.type | text |