Scalable and Improved Algorithms for Individually Fair Clustering

Abstract

We present scalable and improved algorithms for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al and Mahabadi et al. Given $n$ points $P$ in a metric space, let $\delta(x)$ for $x\in P$ be the radius of the smallest ball around $x$ containing at least $\nicefrac nk$ points. In this work, we present two main contributions. We first present local-search algorithms improving prior work along cost and maximum fairness violation. Then we design a fast local-search algorithm that runs in $\tO(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Finally we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.