mlsanityData to 14 Oct 2026

k-means++: few more steps yield constant approximation

arXiv 2002.07784 ↗First posted 18 Feb 2020cs.DS cs.LGcited by 16

Not on the map. Why?

Abstract (arXiv)

The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant eps > 0, with only eps k additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

16 papers.

Sort:

By area:

  1. 2025TTS-VAR: A Test-Time Scaling Framework for Visual Auto-Regressive Generationcited by 15
  2. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  3. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  4. 2021Adaptive Methods for Aggregated Domain Generalizationcited by 6
  5. 2023Multi-Swap k-Means++cited by 5
  6. 2022k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycited by 4
  7. 2022Global k-means++: an effective relaxation of the global k-means clustering algorithmcited by 4
  8. 2025LEANN: A Low-Storage Vector Indexcited by 4
  9. 2024A3S: A General Active Clustering Method with Pairwise Constraintscited by 3
  10. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  11. 2025A statistically consistent measure of semantic uncertainty using Language Modelscited by 2
  12. 2025Improved seeding strategies for k-means and k-GMMcited by 1
4 more
  1. 2023An Analysis of Dα seeding for k-meanscited by 0
  2. 2024Hierarchical Clustering via Local Searchcited by 0
  3. 2026Decoder-Free Supervoxel GNN for Accurate Brain-Tumor Localization in Multi-Modal MRIcited by 0
  4. 2026Randomizing the Number of Centers in k-means++cited by 0