  In this paper, we study k-means++ and k-means++ parallel, 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-means++ parallel. Our results give a better
theoretical justification for why these algorithms perform extremely well in
practice. We also propose a new variant of k-means++ parallel algorithm
(Exponential Race k-means++) that has the same approximation guarantees as
k-means++.
