Review for NeurIPS paper: Improved Guarantees for k-means++ and k-means++ Parallel

Summary and Contributions: In this submission new bounds on the approximation factor of k-means and k-means are presented. The first theoretical contribution is an upper bound of 5(ln(k) 2) on the approximation factor of k-means, which improved upon the previously known upper bound of 8(ln(k) 2) by a constant factor. Then bicriteria approximations are considered, i.e., one uses k-means and k-means to compute clusterings with k Delta clusters for some Delta 0 and compares the costs of these clusterings with those of an optimal k-clustering. Both for k-means and k-means such bicriteria results are already known but in this submission improved bounds are shown. These improved bounds exhibit almost the same asymptotic behavior with respect to Delta as the known bounds but the constants are significantly smaller.