A Constant-Factor Bi-Criteria Approximation Guarantee for $k$-means++
  This paper studies the $k$-means++ algorithm for clustering as well as the
class of $D^\ell$ sampling algorithms to which $k$-means++ belongs. It is shown
that for any constant factor $\beta > 1$, selecting $\beta k$ cluster centers
by $D^\ell$ sampling yields a constant-factor approximation to the optimal
clustering with $k$ centers, in expectation and without conditions on the
dataset. This result extends the previously known $O(\log k)$ guarantee for the
case $\beta = 1$ to the constant-factor bi-criteria regime. It also improves
upon an existing constant-factor bi-criteria result that holds only with
constant probability.
