Tight FPT Approximation for Socially Fair Clustering
  In this work, we study the socially fair $k$-median/$k$-means problem. We are
given a set of points $P$ in a metric space $\mathcal{X}$ with a distance
function $d(.,.)$. There are $\ell$ groups: $P_1,\dotsc,P_{\ell} \subseteq P$.
We are also given a set $F$ of feasible centers in $\mathcal{X}$. The goal in
the socially fair $k$-median problem is to find a set $C \subseteq F$ of $k$
centers that minimizes the maximum average cost over all the groups. That is,
find $C$ that minimizes the objective function $\Phi(C,P) \equiv \max_{j}
\Big\{ \sum_{x \in P_j} d(C,x)/|P_j| \Big\}$, where $d(C,x)$ is the distance of
$x$ to the closest center in $C$. The socially fair $k$-means problem is
defined similarly by using squared distances, i.e., $d^{2}(.,.)$ instead of
$d(.,.)$. The current best approximation guarantee for both the problems is
$O\left( \frac{\log \ell}{\log \log \ell} \right)$ due to Makarychev and
Vakilian [COLT 2021]. In this work, we study the fixed parameter tractability
of the problems with respect to parameter $k$. We design $(3+\varepsilon)$ and
$(9 + \varepsilon)$ approximation algorithms for the socially fair $k$-median
and $k$-means problems, respectively, in FPT (fixed parameter tractable) time
$f(k,\varepsilon) \cdot n^{O(1)}$, where $f(k,\varepsilon) =
(k/\varepsilon)^{{O}(k)}$ and $n = |P \cup F|$. Furthermore, we show that if
Gap-ETH holds, then better approximation guarantees are not possible in FPT
time.
