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

2022/04/11 by Cohen-Addad, Vincent, Esfandiari, Hossein, Mirrokni, Vahab +1 · 4 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2204.04828

Abstract

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, Norouzi-Fard, Svensson, and Ward. 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. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat. 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.

Cited by

• On Tight FPT Time Approximation Algorithms for k-Clustering Problems
• Differentially Private Wasserstein Barycenters
• Provably Small Portfolios for Multiobjective Optimization with Application to Subsidized Facility Location
• Dimension Reduction for Clustering: The Curious Case of Discrete Centers

Related

• Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
• Improved Coresets for Euclidean k-Means
• Faster and Simpler Greedy Algorithm for k-Median and k-Means
• Tight FPT Approximations for k-Median and k-Means
• A Refined Approximation for Euclidean k-Means