{"ID":2859472,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.06130","arxiv_id":"2510.06130","title":"Local Search-based Individually Fair Clustering with Outliers","abstract":"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.","short_abstract":"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. Ho...","url_abs":"https://arxiv.org/abs/2510.06130","url_pdf":"https://arxiv.org/pdf/2510.06130v1","authors":"[\"Binita Maity\",\"Shrutimoy Das\",\"Anirban Dasgupta\"]","published":"2025-10-07T17:06:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}