# Fair Colorful k-Center Clustering

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

## Key facts

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

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

- [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)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [A Global Optimization Algorithm for K-Center Clustering of One Billion Samples](https://mlsanity.com/paper/2301.00061/) (2022)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [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)
- [Covering a Few Submodular Constraints and Applications](https://mlsanity.com/paper/2507.09879/) (2025)

## Abstract (arXiv)

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes.