Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets

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 [30] and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward [1]. Our algorithm achieves an approximation ratio of 2.406 and 5.912 for Euclidean k-median and k-means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. [1] and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat [25].

Our techniques involve a much stronger exploitation of the Euclidean metric than previous work on Euclidean clustering. In addition, we introduce a new method of removing excess centers using a variant of independent sets over graphs that we dub a "nested quasi-independent set". In turn, this technique may be of interest for other optimization problems in Euclidean and ℓ p metric spaces.