Constant-Factor Approximation Algorithms for Socially Fair $k$-Clustering
We study approximation algorithms for the socially fair $(\ell_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\sqrt{6})^p$-approximation with at most
$k+m$ centers (2) a $(5+2\sqrt{6}+\epsilon)^p$-approximation with $k$ centers
in time $n^{2^{O(p)}\cdot m^2}$, and (3) a $(15+6\sqrt{6})^p$ approximation
with $k$ centers in time $k^{m}\cdot\text{poly}(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.