Reviews: A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++

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.