mlsanityData to 7 Oct 2026

Theoretical Analysis of the k-Means Algorithm - A Survey

arXiv 1602.08254 ↗First posted 26 Feb 2016cs.DS cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 0; 2023: 1; 2024: 1; 2025: 1; 2026: 3.

7 papers.

  1. 2024Winner-takes-all learners are geometry-aware conditional density estimatorscited by 6
  2. 2026CRAB: Codebook Rebalancing for Bias Mitigation in Generative Recommendationcited by 4
  3. 2023A two stages Deep Learning Architecture for Model Reduction of Parametric Time-Dependent Problemscited by 1
  4. 2021Neural Networks for Infectious Diseases Detection: Prospects and Challengescited by 0
  5. 2025Determinacc~ao Autom'atica de Limiar de Deteccc~ao de Ataques em Redes de Computadores Utilizando Autoencoderscited by 0
  6. 2026K-Means as a Radial Basis function Network: a Variational and Gradient-based Equivalencecited by 0
  7. 2026Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguisecited by 0