# Local Search-based Individually Fair Clustering with Outliers

arXiv: https://arxiv.org/abs/2510.06130 · HTML: https://mlsanity.com/paper/2510.06130/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2025.

## Built on by (most cited first, 1 of 1)

- [Individual Fairness in Hierarchical Clustering](https://mlsanity.com/paper/2608.25586/) (2026)

## Abstract (arXiv)

In this paper, 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., which requires that each of the n points in the dataset must have one of the k centers within its n/k nearest neighbors. However, if the dataset is known to contain outliers, the set of fair centers obtained under this definition might be suboptimal for non-outlier points. 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 claims experimentally on a set of real-world datasets.