## Abstract

We present polynomial upper and lower bounds on the number of iterations performed by the fc-means method (a.k.a. Lloyd's method) for k-means clustering. Our upper bounds are polynomial in the number of points, number of clusters, and the spread of the point set. We also present a lower bound, showing that in the worst case the k-means heuristic needs to perform Ω(n) iterations, for n points on the real line and two centers. Surprisingly, the spread of the point set in this construction is polynomial. This is the first construction showing that the k-means heuristic requires more than a polylogarithmic number of iterations. Furthermore, we present two alternative algorithms, with guaranteed performance, which are simple variants of the k-means method.

Original language | English (US) |
---|---|

Pages | 877-885 |

Number of pages | 9 |

State | Published - 2005 |

Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |

### Other

Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Vancouver, BC |

Period | 1/23/05 → 1/25/05 |

## ASJC Scopus subject areas

- Software
- General Mathematics