# A New Notion of Individually Fair Clustering: α-Equitable k-Center

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 18 of 18)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination](https://mlsanity.com/paper/1408.6491/) (2014)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Envy-Free Classification](https://mlsanity.com/paper/1809.08700/) (2018)

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

- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [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)
- [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)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [A review of clustering models in educational data science towards fairness-aware learning](https://mlsanity.com/paper/2301.03421/) (2023)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [A Computational Approach to Improving Fairness in K-means Clustering](https://mlsanity.com/paper/2505.22984/) (2025)
- [Comparing Apples to Oranges: Learning Similarity Functions for Data Produced by Different Distributions](https://mlsanity.com/paper/2208.12731/) (2022)
- [Cluster-level Group Representativity Fairness in k-means Clustering](https://mlsanity.com/paper/2212.14467/) (2022)
- [Efficient k-means with Individual Fairness via Exponential Tilting](https://mlsanity.com/paper/2406.16557/) (2024)
- [FACROC: a fairness measure for FAir Clustering through ROC curves](https://mlsanity.com/paper/2503.00854/) (2025)
- [A Group-Based Resource Allocation Model for the Fractional Knapsack Problem](https://mlsanity.com/paper/2609.06470/) (2026)

## Abstract (arXiv)

Clustering is a fundamental problem in unsupervised machine learning, and fair variants of it have recently received significant attention due to its societal implications. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point j has a set of other points Sj that it perceives as similar to itself, and it feels that it is fairly treated if the quality of service it receives in the solution is α-close (in a multiplicative sense, for a given α ≥ 1) to that of the points in Sj. We begin our study by answering questions regarding the structure of the problem, namely for what values of α the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of α, we provide efficient and easily-implementable approximation algorithms for the k-center objective, which in certain cases enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.