Improved Guarantees for k-means++ and k-means++ Parallel
Not on the map. Why?
Abstract (arXiv)
In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++.
Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Oct 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 3; 2023: 5; 2024: 0; 2025: 1; 2026: 2.
12 papers.
- 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
- 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
- 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
- 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graphcited by 10
- 2022How to Use K-means for Big Data Clustering?cited by 7
- 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
- 2023Initializing Services in Interactive ML Systems for Diverse Userscited by 5
- 2025Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Datasetcited by 4
- 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
- 2023An Analysis of Dα seeding for k-meanscited by 0
- 2026Data-Native Global Optimization for Big Data K-means Clusteringcited by 0
- 2026Randomizing the Number of Centers in k-means++cited by 0
- 2026Randomizing the Number of Centers in k-means++28 Jul 2026
- 2026Data-Native Global Optimization for Big Data K-means Clustering17 Jul 2026
- 2025Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Dataset26 Feb 2025
- 2023Initializing Services in Interactive ML Systems for Diverse Users19 Dec 2023
- 2023An Analysis of Dα seeding for k-means20 Oct 2023
- 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time14 Sep 2023
- 2023Online Adaptive Mahalanobis Distance Estimation2 Sep 2023
- 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph10 Mar 2023
- 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability15 Oct 2022
- 2022A Nearly Tight Analysis of Greedy k-means++16 Jul 2022
- 2022How to Use K-means for Big Data Clustering?14 Apr 2022
- 2021Explainable k-means. Don't be greedy, plant bigger trees!4 Nov 2021