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 sampling algorithms to which k-means++ belongs. It is shown that for any constant factor β > 1, selecting βk cluster centers by D 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 β = 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.
The authors consider the famous k-means problem; Given a set of points P in a metric space with distance function d, the goal is to output k centers such that the sum of the squared distances of each point to its closest center is minimized.  The authors focus on bi-criteria approximation algorithms; The algorithms are allowed to output beta k centers (instead of k) and the approximation ratio is computed with respect to the optimal solution (that uses k centers). In the general case, the optimal solution using k centers can be arbitrarily worse than the solution using beta k centers for beta > 1.  The goal of the paper is to prove that a algorithms of a certain kind -- called D-sampling algorithms -- produce constant factor bi-criteria approximation.  D-sampling algorithms iteratively pick the set of centers at random according to some probability distribution based on the cost of the points with respect to the current set of centers.  This work is directly in the line of D. Arthur and S. Vassilvitskii [4] whose proved that the D-sampling algorithms produce an O(log k)-approximation (not bi-criteria). The main result of this work is to analyze the D-sampling algorithms in the bi-criteria regime.  More concretely, they show an approximation guarantee of 1+min{O((k-2)/(beta-1)k), log k} for D-sampling algorithms allowing beta k centers.
I find the result interesting and it is a nice addition to the literature but I do not find it very surprising in itself. Intuitively, D-sampling algorithms do not need to know k in advance, thus, if the algorithm is efficient for finding k centers (which we know it is from [4]), allowing it to pick beta k centers "has to" make the cost decrease significantly (as if the algorithm was solving an instance of the problem for beta k centers). Moreover, the result was known in the constant probability case (rather than expectation).  One of the main issue of this paper is the lack of comparison with previous work. There are at least 4 recent papers that tackle the k-means problem (and two of them tackle the bi-criteria version) and 3 of them are not cited (all on arxiv): 1-- A bi-criteria approximation algorithm for k Means. [20] 2-- On Variants of k-means Clustering. 3-- Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics. 4-- Local Search Yields a PTAS for $k$-Means in Doubling Metrics.  How does it compare to the recent bi-criteria approximation algorithms of 1 and 2? Does D-sampling algorithms provide a better bi-criteria approximation? It is stated that the algorithms in 1 have dependency in n^O(log(1/epsilon)/epsilon^2). However, local search with neighborhood of size 1 has running time O(n k) (and constant factor approximation guarantee) which is comparable to D-sampling algorithms. Thus, according to the sentence "The main difference between Corollary 1 and the bounds in [20] is the extra factor of r_D^l." it seens that D-sampling is worse.  Another issue is about the motivation of this work. Are bi-criteria D-sampling algorithms used in practice? This is true for not bi-criteria versions, are there references for the bi-criteria case?  One interesting question is whether allowing an additional number of clusters, say k + c, would be sufficient to significantly improve the approximation ratio of log(k) (this is true for the case of k-median for example).  Other relevant remark:  "Alternatively, a simpler algorithm (like k-means++) that has a constant-factor bi-criteria guarantee would ensure that the trade-off curve generated by this algorithm deviates by no more than constant factors along both axes from the optimal curve."  It is shown in 2 that local search (which is rather simple) is such an algorithm and this holds even when centers are restricted to be input points (at the cost of a constant factor).