mlsanityData to 7 Oct 2026

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

arXiv 2407.11217 ↗First posted 15 Jul 2024cs.DS cs.AIcited by 0

Not on the map. Why?

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.

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

Builds on

17 of 45 references.

References · 17

  1. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  2. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  3. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  4. 2021A New Coreset Framework for Clusteringcited by 38
  5. 2017Constant Approximation for k-Median and k-Means with Outliers via Iterative Roundingcited by 25
  6. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  7. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  8. 2018Near-Linear Time Approximation Schemes for Clustering in Doubling Metricscited by 14
  9. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  10. 2017On the Local Structure of Stable Clustering Instancescited by 13
  11. 2017A Fast Approximation Scheme for Low-Dimensional k-Meanscited by 10
  12. 2020Fast and Accurate k-means++ via Rejection Samplingcited by 10
5 more
  1. 2017Constant-Factor Approximation for Ordered k-Mediancited by 8
  2. 2021An Improved Local Search Algorithm for k-Mediancited by 8
  3. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  4. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  5. 2019On Strong Diameter Padded Decompositionscited by 1

Built on by

Not cited yet.