The $k$-means++ algorithm is composed of two parts:
- Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling.
- Expectation maximization part: the standard $k$-means algorithm (or Lloyd's algorithm) is run with these initialized centers.
In the k-means++ paper, the authors show that the $k$-means algorithm can not perform better than $O(\log k)$-approximation in expectation (see Section 4 of the same paper). However, they only give this lower bound for the initialization part without considering the expectation-maximization part. Does that make their lower bound argument incorrect/incomplete? If so, the $k$-means++ algorithm might give better than $O(\log k)$-approximation and the proven lower bound is misleading.