# Faster and Simpler Greedy Algorithm for k-Median and k-Means

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 45 references that are in the map.
- First posted on arXiv 15 Jul 2024.

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

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [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)
- [Constant-Factor Approximation for Ordered k-Median](https://mlsanity.com/paper/1711.01972/) (2017)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [On Strong Diameter Padded Decompositions](https://mlsanity.com/paper/1906.09783/) (2019)

## Abstract (arXiv)

Clustering problems such as k-means and k-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.