Greedy bi-criteria approximations for $k$-medians and $k$-means
  This paper investigates the following natural greedy procedure for clustering
in the bi-criterion setting: iteratively grow a set of centers, in each round
adding the center from a candidate set that maximally decreases clustering
cost. In the case of $k$-medians and $k$-means, the key results are as follows.
  $\bullet$ When the method considers all data points as candidate centers,
then selecting $\mathcal{O}(k\log(1/\varepsilon))$ centers achieves cost at
most $2+\varepsilon$ times the optimal cost with $k$ centers.
  $\bullet$ Alternatively, the same guarantees hold if each round samples
$\mathcal{O}(k/\varepsilon^5)$ candidate centers proportionally to their
cluster cost (as with $\texttt{kmeans++}$, but holding centers fixed).
  $\bullet$ In the case of $k$-means, considering an augmented set of
$n^{\lceil1/\varepsilon\rceil}$ candidate centers gives $1+\varepsilon$
approximation with $\mathcal{O}(k\log(1/\varepsilon))$ centers, the entire
algorithm taking
$\mathcal{O}(dk\log(1/\varepsilon)n^{1+\lceil1/\varepsilon\rceil})$ time, where
$n$ is the number of data points in $\mathbb{R}^d$.
  $\bullet$ In the case of Euclidean $k$-medians, generating a candidate set
via $n^{\mathcal{O}(1/\varepsilon^2)}$ executions of stochastic gradient
descent with adaptively determined constraint sets will once again give
approximation $1+\varepsilon$ with $\mathcal{O}(k\log(1/\varepsilon))$ centers
in $dk\log(1/\varepsilon)n^{\mathcal{O}(1/\varepsilon^2)}$ time.
  Ancillary results include: guarantees for cluster costs based on powers of
metrics; a brief, favorable empirical evaluation against $\texttt{kmeans++}$;
data-dependent bounds allowing $1+\varepsilon$ in the first two bullets above,
for example with $k$-medians over finite metric spaces.
