  We study the fair variant of the classic $k$-median problem introduced by
Chierichetti et al. [2017]. In the standard $k$-median problem, given an input
pointset $P$, the goal is to find $k$ centers $C$ and assign each input point
to one of the centers in $C$ such that the average distance of points to their
cluster center is minimized.
  In the fair variant of $k$-median, the points are colored, and the goal is to
minimize the same average distance objective while ensuring that all clusters
have an "approximately equal" number of points of each color.
  Chierichetti et al. proposed a two-phase algorithm for fair $k$-clustering.
In the first step, the pointset is partitioned into subsets called fairlets
that satisfy the fairness requirement and approximately preserve the $k$-median
objective. In the second step, fairlets are merged into $k$ clusters by one of
the existing $k$-median algorithms. The running time of this algorithm is
dominated by the first step, which takes super-quadratic time.
  In this paper, we present a practical approximate fairlet decomposition
algorithm that runs in nearly linear time. Our algorithm additionally allows
for finer control over the balance of resulting clusters than the original
work. We complement our theoretical bounds with empirical evaluation.
