# A Notion of Individual Fairness for Clustering

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

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

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clustering](https://mlsanity.com/paper/2209.12756/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Holistic Survey of Privacy and Fairness in Machine Learning](https://mlsanity.com/paper/2307.15838/) (2023)
- [Models and Mechanisms for Spatial Data Fairness](https://mlsanity.com/paper/2204.01880/) (2022)
- [Fair Spatial Indexing: A paradigm for Group Spatial Fairness](https://mlsanity.com/paper/2302.02306/) (2023)
- [Exploring Rawlsian Fairness for K-Means Clustering](https://mlsanity.com/paper/2205.02052/) (2022)
- [Fair Clustering via Hierarchical Fair-Dirichlet Process](https://mlsanity.com/paper/2305.17557/) (2023)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [AI and Core Electoral Processes: Mapping the Horizons](https://mlsanity.com/paper/2302.03774/) (2023)
- [A Model Ensemble-Based Post-Processing Framework for Fairness-Aware Prediction](https://mlsanity.com/paper/2603.18838/) (2026)
- [UniFair: A unified fair clustering approach based on separation and compactness](https://mlsanity.com/paper/2606.04777/) (2026)

## Abstract (arXiv)

A common distinction in fair machine learning, in particular in fair classification, is between group fairness and individual fairness. In the context of clustering, group fairness has been studied extensively in recent years; however, individual fairness for clustering has hardly been explored. In this paper, we propose a natural notion of individual fairness for clustering. Our notion asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. We study several questions related to our proposed notion of individual fairness. On the negative side, we show that deciding whether a given data set allows for such an individually fair clustering in general is NP-hard. On the positive side, for the special case of a data set lying on the real line, we propose an efficient dynamic programming approach to find an individually fair clustering. For general data sets, we investigate heuristics aimed at minimizing the number of individual fairness violations and compare them to standard clustering approaches on real data sets.