Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
This work addresses clustering efficiency for researchers and practitioners, but it is incremental as it builds on an existing greedy algorithm.
The paper tackles the problem of simplifying and speeding up the recursive greedy algorithm for k-median and k-means clustering, achieving faster implementation that matches or improves state-of-the-art performance in graph metrics or Euclidean space.
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.