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 $��(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.

The new version gives tight approximation results. However, the old version uses techniques that work in the streaming setting albeit at the cost of weaker approximation guarantees. So, readers interested in the streaming setting may want to see the older version