Constant-Factor Approximation Algorithms for Socially Fair k-Clustering

2022/06/22 by Ghadiri, Mehrdad, Singh, Mohit, Vempala, Santosh S. · 1 citation
#62H30 #68W25 #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.1 #I.5.3 #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2206.11210

Abstract

We study approximation algorithms for the socially fair (ℓ_p, k)-clustering problem with m groups, whose special cases include the socially fair k-median (p=1) and socially fair k-means (p=2) problems. We present (1) a polynomial-time (5+2√(6))^p-approximation with at most k+m centers (2) a (5+2√(6)+ε)^p-approximation with k centers in time n^2^O(p)⋅ m², and (3) a (15+6√(6))^p approximation with k centers in time k^m\cdotpoly(n). The first result is obtained via a refinement of the iterative rounding method using a sequence of linear programs. The latter two results are obtained by converting a solution with up to k+m centers to one with k centers using sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing bicriteria algorithms as well as exactly k center approximation algorithms on benchmark datasets, and find that our algorithms also outperform existing methods in practice.

Cited by

• Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering

Related

• Approximation Algorithms for Socially Fair Clustering
• A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering
• Tight FPT Approximation for Socially Fair Clustering
• Approximation Algorithms for Fair Range Clustering
• Improved Approximation Algorithms for Individually Fair Clustering