FPT Approximation for Socially Fair Clustering

06/12/2021

∙

by   Dishant Goyal, et al.

∙

0

∙

share

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.