# A Constant Approximation for Colorful k-Center

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2019.

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

- [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)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Clustering via Hierarchical Fair-Dirichlet Process](https://mlsanity.com/paper/2305.17557/) (2023)
- [Bicriteria Approximation Algorithms for Priority Matroid Median](https://mlsanity.com/paper/2210.01888/) (2022)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Covering a Few Submodular Constraints and Applications](https://mlsanity.com/paper/2507.09879/) (2025)

## Abstract (arXiv)

In this paper, we consider the colorful k-center problem, which is a generalization of the well-known k-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius ρ, such that with k balls of radius ρ, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a "pseudo-approximation" algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.