FPT Approximation for Socially Fair Clustering

06/12/2021
āˆ™
by   Dishant Goyal, et al.
āˆ™
0
āˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset