Fair Representation Clustering with Several Protected Classes

Abstract

We study the problem of fair k-median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation k-median problem, we are given a set of points X in a metric space. Each point x X belongs to one of groups. Further, we are given fair representation parameters _j and _j for each group j []. We say that a k-clustering C_1, , C_k fairly represents all groups if the number of points from group j in cluster C_i is between _j |C_i| and _j |C_i| for every j[] and i [k]. The goal is to find a set C of k centers and an assignment : X C such that the clustering defined by (C, ) fairly represents all groups and minimizes the _1-objective _x X d(x, (x)). We present an O( k)-approximation algorithm that runs in time n^O(). Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and . We also consider an important special case of the problem where _j = _j = f_jf and f_j, f N for all j []. For this special case, we present an O( k)-approximation algorithm that runs in (kf)^O() n + poly(n) time.

Tasks

Reproductions