Individually Fair Clustering with Outliers

We present a local search-based algorithm for individually fair clustering in the presence of outliers. We consider the individual fairness definition proposed in (Jung et al. 2020), which requires that each of the $n$ points in the dataset must have one of the $k$ centers within its $n/k$ neighbors. However, if the dataset is known to contain outliers, the set of fair centers obtained might be suboptimal. In order to address this issue, we propose a method that discards a set of points marked as outliers and computes the set of fair centers for the remaining non-outlier points. Our method utilizes a randomized variant of local search, which makes it scalable to large datasets. We also provide an approximation guarantee of our method as well as a bound on the number of outliers discarded. Additionally, we demonstrate our experiments on a set of real-world datasets.