# A Technique for Obtaining True Approximations for k-Center with Covering Constraints

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

## Key facts

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

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

- [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)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Fair Disaster Containment via Graph-Cut Problems](https://mlsanity.com/paper/2106.05424/) (2021)
- [Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response](https://mlsanity.com/paper/2202.04705/) (2022)
- [Differentially Private Partial Set Cover with Applications to Facility Location](https://mlsanity.com/paper/2207.10240/) (2022)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (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)

There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors---settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan---and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P neq NP. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.