Improved guarantees for k-means++ and k-means++ parallel

Konstantin Makarychev*, Aravind Reddy, Liren Shan

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

15 Scopus citations


In this paper, we study k-means++ and k-meansk, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-meansk. Our results give a better theoretical justification for why these algorithms perform extremely well in practice.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2020
Event34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online
Duration: Dec 6 2020Dec 12 2020

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Improved guarantees for k-means++ and k-means++ parallel'. Together they form a unique fingerprint.

Cite this