We study data clustering problems with $\ell_p$-norm objectives (e.g.
$k$-Median and $k$-Means) in the context of individual fairness. The dataset
consists of $n$ points, and we want to find $k$ centers such that (a) the
objective is minimized, while (b) respecting the individual fairness constraint
that every point $v$ has a center within a distance at most $r(v)$, where
$r(v)$ is $v$'s distance to its $(n/k)$th nearest point. Jung, Kannan, and Lutz
[FORC 2020] introduced this concept and designed a clustering algorithm with
provable (approximate) fairness and objective guarantees for the $\ell_\infty$
or $k$-Center objective. Mahabadi and Vakilian [ICML 2020] revisited this
problem to give a local-search algorithm for all $\ell_p$-norms. Empirically,
their algorithms outperform Jung et. al.'s by a large margin in terms of cost
(for $k$-Median and $k$-Means), but they incur a reasonable loss in fairness.
In this paper, our main contribution is to use Linear Programming (LP)
techniques to obtain better algorithms for this problem, both in theory and in
practice. We prove that by modifying known LP rounding techniques, one gets a
worst-case guarantee on the objective which is much better than in MV20, and
empirically, this objective is extremely close to the optimal. Furthermore, our
theoretical fairness guarantees are comparable with MV20 in theory, and
empirically, we obtain noticeably fairer solutions. Although solving the LP
{\em exactly} might be prohibitive, we demonstrate that in practice, a simple
sparsification technique drastically improves the run-time of our algorithm.

运用线性规划和局部搜索算法解决在数据聚类问题中，$\ell_p$-range 目标下的个体公平问题。通过修改 LP 理论和结合局部搜索算法实践，实现更优算法，并在实验中展现了出众的表现。