The paper presents a new algorithm for speeding up k-means++ algorithms with rigorous theoretical guarantees. It is quite surprising that they can improve the running time to \tilde{O}(nd+n^{1+\eps}) when even one round of k-means++ algorithm takes O(ndk) time. The main shortcoming is the performance gain is only visible for large k. However, I think the large k regime is very interesting and does appear in practice. The authors should add discussion about aspect ratio and the new experiments as pointed out by them in the rebuttal.