  The famous $k$-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is
the most popular way of solving the $k$-means problem in practice. The
algorithm is very simple: it samples the first center uniformly at random and
each of the following $k-1$ centers is then always sampled proportional to its
squared distance to the closest center so far. Afterward, Lloyd's iterative
algorithm is run. The $k$-means++ algorithm is known to return a $\Theta(\log
k)$ approximate solution in expectation.
  In their seminal work, Arthur and Vassilvitskii [SODA 2007] asked about the
guarantees for its following \emph{greedy} variant: in every step, we sample
$\ell$ candidate centers instead of one and then pick the one that minimizes
the new cost. This is also how $k$-means++ is implemented in e.g. the popular
Scikit-learn library [Pedregosa et al.; JMLR 2011].
  We present nearly matching lower and upper bounds for the greedy $k$-means++:
We prove that it is an $O(\ell^3 \log^3 k)$-approximation algorithm. On the
other hand, we prove a lower bound of $\Omega(\ell^3 \log^3 k / \log^2(\ell\log
k))$. Previously, only an $\Omega(\ell \log k)$ lower bound was known
[Bhattacharya, Eube, R\"oglin, Schmidt; ESA 2020] and there was no known upper
bound.
