Jump to Content

Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets

Hossein Esfandiari
Shyam Narayanan
54rd Annual ACM Symposium on Theory of Computing (STOC'22) (2022)
Google Scholar


Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean $k$-median and $k$-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian et al.. Our algorithm achieves an approximation ratio of respectively 2.40... and 5.95... for Euclidean $k$-median and $k$-means improving upon the 2.60... of Ahmadian et al. and the 6.12.. of Grandoni et al..