mlsanityData to 14 Oct 2026

A Faster k-means++ Algorithm

arXiv 2211.15118 ↗First posted 28 Nov 2022cs.DS cs.LGcited by 4

Not on the map. Why?

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.

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

19 of 58 references.

References · 19

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  3. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  4. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  5. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  6. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  7. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  8. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  9. 2022A Faster Small Treewidth SDP Solvercited by 36
  10. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  11. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  12. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
7 more
  1. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  2. 2016Local Search Yields a PTAS for k-Means in Doubling Metricscited by 13
  3. 2016Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metricscited by 11
  4. 2017A Fast Approximation Scheme for Low-Dimensional k-Meanscited by 10
  5. 2020Fast and Accurate k-means++ via Rejection Samplingcited by 10
  6. 2016A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++cited by 8
  7. 2015On Variants of k-means Clusteringcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 2.

4 papers.

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  3. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  4. 2024Accelerating the k-means++ Algorithm by Using Geometric Informationcited by 0