Individual Fairness for $k$-Clustering
  We give a local search based algorithm for $k$-median and $k$-means (and more
generally for any $k$-clustering with $\ell_p$ norm cost function) from the
perspective of individual fairness. More precisely, for a point $x$ in a point
set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of
radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively,
if a set of $k$ random points are chosen from $P$ as centers, every point $x\in
P$ expects to have a center within radius $r(x)$. An individually fair
clustering provides such a guarantee for every point $x\in P$. This notion of
fairness was introduced in [Jung et al., 2019] where they showed how to get an
approximately feasible $k$-clustering with respect to this fairness condition.
  In this work, we show how to get a bicriteria approximation for fair
$k$-clustering: The $k$-median ($k$-means) cost of our solution is within a
constant factor of the cost of an optimal fair $k$-clustering, and our solution
approximately satisfies the fairness condition (also within a constant factor).
Further, we complement our theoretical bounds with empirical evaluation.
