- Hossein Esfandiari
- Shyam Narayanan
- Vahab Mirrokni
- Vincent Pierre Cohen-addad
54rd Annual ACM Symposium on Theory of Computing (STOC'22) (2022)
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..
We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work