# Fair Coresets and Streaming Algorithms for Fair k-Means Clustering

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2018.

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

- [Modeling Techniques for Machine Learning Fairness: A Survey](https://mlsanity.com/paper/2111.03015/) (2021)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Fairness-Aware Unsupervised Feature Selection](https://mlsanity.com/paper/2106.02216/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Perceptual Fairness in Image Restoration](https://mlsanity.com/paper/2405.13805/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Fair Clustering with Clusterlets](https://mlsanity.com/paper/2505.06259/) (2025)
- [Deterministic Coreset Construction via Adaptive Sensitivity Trimming](https://mlsanity.com/paper/2508.18340/) (2025)
- [UniFair: A unified fair clustering approach based on separation and compactness](https://mlsanity.com/paper/2606.04777/) (2026)
- [Beyond Binary: Continuous State Optimization with Graph-Structured Objectives](https://mlsanity.com/paper/2608.09366/) (2026)

## Abstract (arXiv)

We study fair clustering problems as proposed by Chierichetti et al. (NIPS 2017). Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable and show how to compute them in a streaming setting. Furthermore, we propose a variant of Lloyd's algorithm that computes fair clusterings and extend it to a fair k-means++ clustering algorithm. We implement these algorithms and provide empirical evidence that the combination of our approximation algorithms and the coreset construction yields a scalable algorithm for fair k-means clustering.