# Theoretical Analysis of the k-Means Algorithm - A Survey

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2016.

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

- [Winner-takes-all learners are geometry-aware conditional density estimators](https://mlsanity.com/paper/2406.04706/) (2024)
- [CRAB: Codebook Rebalancing for Bias Mitigation in Generative Recommendation](https://mlsanity.com/paper/2604.05113/) (2026)
- [A two stages Deep Learning Architecture for Model Reduction of Parametric Time-Dependent Problems](https://mlsanity.com/paper/2301.09926/) (2023)
- [Neural Networks for Infectious Diseases Detection: Prospects and Challenges](https://mlsanity.com/paper/2112.03571/) (2021)
- [Determinacc~ao Autom'atica de Limiar de Deteccc~ao de Ataques em Redes de Computadores Utilizando Autoencoders](https://mlsanity.com/paper/2506.14937/) (2025)
- [K-Means as a Radial Basis function Network: a Variational and Gradient-based Equivalence](https://mlsanity.com/paper/2603.04625/) (2026)
- [Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise](https://mlsanity.com/paper/2607.25190/) (2026)

## Abstract (arXiv)

The k-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly difficult and can lead to deep insights that can be used to improve the algorithm. In this paper we survey the recent results in this direction as well as several extension of the basic k-means method.