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 š³ with a distance function d(.,.). There are ā groups: P_1,ā¦,P_āā P. We are also given a set F of feasible centers in š³. The goal of the socially fair k-median problem is to find a set C ā 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) ā”max_jā_x ā P_j d(C,x)/|P_j|, 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(.,.). In this work, we design (5+Īµ) and (33 + Īµ) approximation algorithms for the socially fair k-median and k-means problems, respectively. For the parameters: k and ā, the algorithms have an FPT (fixed parameter tractable) running time of f(k,ā,Īµ) Ā· n for f(k,ā,Īµ) = 2^O(k ā/Īµ) and n = |P āŖ F|. We also study a special case of the problem where the centers are allowed to be chosen from the point set P, i.e., P ā F. For this special case, our algorithms give better approximation guarantees of (4+Īµ) and (18+Īµ) for the socially fair k-median and k-means problems, respectively. Furthermore, we convert these algorithms to constant pass log-space streaming algorithms. Lastly, we show FPT hardness of approximation results for the problem with a small gap between our upper and lower bounds.
READ FULL TEXT