# Improved Guarantees for k-means++ and k-means++ Parallel

arXiv: https://arxiv.org/abs/2010.14487 · HTML: https://mlsanity.com/paper/2010.14487/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

## Built on by (most cited first, 12 of 12)

- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [How to Use K-means for Big Data Clustering?](https://mlsanity.com/paper/2204.07485/) (2022)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)
- [Initializing Services in Interactive ML Systems for Diverse Users](https://mlsanity.com/paper/2312.11846/) (2023)
- [Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Dataset](https://mlsanity.com/paper/2502.18955/) (2025)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [An Analysis of Dα seeding for k-means](https://mlsanity.com/paper/2310.13474/) (2023)
- [Data-Native Global Optimization for Big Data K-means Clustering](https://mlsanity.com/paper/2607.15835/) (2026)
- [Randomizing the Number of Centers in k-means++](https://mlsanity.com/paper/2607.26202/) (2026)

## Abstract (arXiv)

In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++.