Improved Approximation Algorithms for Individually Fair Clustering
  We consider the $k$-clustering problem with $\ell_p$-norm cost, which
includes $k$-median, $k$-means and $k$-center, under an individual notion of
fairness proposed by Jung et al. [2020]: given a set of points $P$ of size $n$,
a set of $k$ centers induces a fair clustering if every point in $P$ has a
center among its $n/k$ closest neighbors. Mahabadi and Vakilian [2020]
presented a $(p^{O(p)},7)$-bicriteria approximation for fair clustering with
$\ell_p$-norm cost: every point finds a center within distance at most $7$
times its distance to its $(n/k)$-th closest neighbor and the $\ell_p$-norm
cost of the solution is at most $p^{O(p)}$ times the cost of an optimal fair
solution.
  In this work, for any $\varepsilon>0$, we present an improved $(16^p
+\varepsilon,3)$-bicriteria for this problem. Moreover, for $p=1$ ($k$-median)
and $p=\infty$ ($k$-center), we present improved cost-approximation factors
$7.081+\varepsilon$ and $3+\varepsilon$ respectively. To achieve our
guarantees, we extend the framework of [Charikar et al., 2002, Swamy, 2016] and
devise a $16^p$-approximation algorithm for the facility location with
$\ell_p$-norm cost under matroid constraint which might be of an independent
interest.
  Besides, our approach suggests a reduction from our individually fair
clustering to a clustering with a group fairness requirement proposed by
Kleindessner et al. [2019], which is essentially the median matroid problem
[Krishnaswamy et al., 2011].
