# A Faster k-means++ Algorithm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 58 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 19 of 19)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [A Fast Approximation Scheme for Low-Dimensional k-Means](https://mlsanity.com/paper/1708.07381/) (2017)
- [Fast and Accurate k-means++ via Rejection Sampling](https://mlsanity.com/paper/2012.11891/) (2020)
- [A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++](https://mlsanity.com/paper/1605.04986/) (2016)
- [On Variants of k-means Clustering](https://mlsanity.com/paper/1512.02985/) (2015)

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

- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Accelerating the k-means++ Algorithm by Using Geometric Information](https://mlsanity.com/paper/2408.13189/) (2024)

## Abstract (arXiv)

k-means++ is an important algorithm for choosing initial cluster centers for the k-means clustering algorithm. In this work, we present a new algorithm that can solve the k-means++ problem with nearly optimal running time. Given n data points in ℝd, the current state-of-the-art algorithm runs in widetildeO(k ) iterations, and each iteration takes widetildeO(nd k) time. The overall running time is thus widetildeO(n d k2). We propose a new algorithm textscFastKmeans++ that only takes in widetildeO(nd + nk2) time, in total.