# Approximate Group Fairness for Clustering

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

## Key facts

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

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

- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [Proportional Selection in Networks](https://mlsanity.com/paper/2502.03545/) (2025)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)
- [A Model Ensemble-Based Post-Processing Framework for Fairness-Aware Prediction](https://mlsanity.com/paper/2603.18838/) (2026)

## Abstract (arXiv)

We incorporate group fairness into the algorithmic centroid clustering problem, where k centers are to be located to serve n agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al., ICML 2019] as em core fairness, and k-clustering is in the core if no coalition containing at least n/k agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly.