Constant-Factor Approximation Algorithms for Socially Fair k-Clustering

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+26)^p-approximation with at most k+m centers (2) a (5+26+)^p-approximation with k centers in time n^2^O(p) m^2, and (3) a (15+66)^p approximation with k centers in time k^mpoly(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.

Tasks

Reproductions