# How to Solve Fair k-Center in Massive Data Models

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

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

- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Streaming Algorithms for Diversity Maximization with Fairness Constraints](https://mlsanity.com/paper/2208.00194/) (2022)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds](https://mlsanity.com/paper/2203.02502/) (2022)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering](https://mlsanity.com/paper/2609.06384/) (2026)

## Abstract (arXiv)

Fueled by massive data, important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new streaming and distributed algorithms for the fair k-center problem that models fair data summarization. The streaming and distributed models of computation have an attractive feature of being able to handle massive data sets that do not fit into main memory. Our main contributions are: (a) the first distributed algorithm; which has provably constant approximation ratio and is extremely parallelizable, and (b) a two-pass streaming algorithm with a provable approximation guarantee matching the best known algorithm (which is not a streaming algorithm). Our algorithms have the advantages of being easy to implement in practice, being fast with linear running times, having very small working memory and communication, and outperforming existing algorithms on several real and synthetic data sets. To complement our distributed algorithm, we also give a hardness result for natural distributed algorithms, which holds for even the special case of k-center.