Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.06130 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909829955584000 |
|---|---|
| author | Maity, Binita Das, Shrutimoy Dasgupta, Anirban |
| author_facet | Maity, Binita Das, Shrutimoy Dasgupta, Anirban |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06130 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Search-based Individually Fair Clustering with Outliers Maity, Binita Das, Shrutimoy Dasgupta, Anirban Data Structures and Algorithms 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. |
| title | Local Search-based Individually Fair Clustering with Outliers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.06130 |