Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson +1

Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algori…