Better Algorithms for Individually Fair k -Clustering

We study data clustering problems with \ell_p -norm objectives (e.g. 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 \textsc{ k -Center} objective. Empirically, their algorithms outperform Jung et. 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.