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 X with a distance function d(.,.). There are ℓ groups: P1,dotsc,Pℓ subseteq P. We are also given a set F of feasible centers in 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 maxj Big sumx ∈ Pj d(C,x)/|Pj| 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., d2(.,.) instead of d(.,.). The current best approximation guarantee for both the problems is Oleft( fraclog ℓlog log ℓ 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) · nO(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.