Fair Representation Clustering with Several Protected Classes
  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\in X$ belongs to one of $\ell$ groups. Further, we are
given fair representation parameters $\alpha_j$ and $\beta_j$ for each group
$j\in [\ell]$. We say that a $k$-clustering $C_1, \cdots, C_k$ fairly
represents all groups if the number of points from group $j$ in cluster $C_i$
is between $\alpha_j |C_i|$ and $\beta_j |C_i|$ for every $j\in[\ell]$ and
$i\in [k]$. The goal is to find a set $\mathcal{C}$ of $k$ centers and an
assignment $\phi: X\rightarrow \mathcal{C}$ such that the clustering defined by
$(\mathcal{C}, \phi)$ fairly represents all groups and minimizes the
$\ell_1$-objective $\sum_{x\in X} d(x, \phi(x))$.
  We present an $O(\log k)$-approximation algorithm that runs in time
$n^{O(\ell)}$. 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 $\ell$. We also consider an important special
case of the problem where $\alpha_j = \beta_j = \frac{f_j}{f}$ and $f_j, f \in
\mathbb{N}$ for all $j\in [\ell]$. For this special case, we present an $O(\log
k)$-approximation algorithm that runs in $(kf)^{O(\ell)}\log n + poly(n)$ time.
