# On the Hardness of Approximation of the Fair k-Center Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Algorithmic Fairness](https://mlsanity.com/paper/2001.09784/) (2020)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Diversity-aware k-median : Clustering with fair center representation](https://mlsanity.com/paper/2106.11696/) (2021)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Clustering with fair-center representation: parameterized approximation algorithms and heuristics](https://mlsanity.com/paper/2112.07030/) (2021)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [On the Fixed-Parameter Tractability of Capacitated Clustering](https://mlsanity.com/paper/2208.14129/) (2022)
- [Fair Column Subset Selection](https://mlsanity.com/paper/2306.04489/) (2023)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [Improved approximation algorithms for two Euclidean k-Center variants](https://mlsanity.com/paper/2112.05083/) (2021)
- [Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms](https://mlsanity.com/paper/2505.15905/) (2025)
- [Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information](https://mlsanity.com/paper/2512.24934/) (2025)

## Abstract (arXiv)

In this work, we study the hardness of approximation of the fair k-center problem. In this problem, we are given a set of data points in a metric space that is partitioned into groups and the task is to choose a subset of k-data points, called centers, such that a prescribed number of data points from each group are chosen while minimizing the maximum distance from any point to its closest center. Although a polynomial-time 3-approximation is known for fair k-center in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the classical unconstrained k-center problem admits a polynomial-time factor-2 approximation. We resolve this open question by proving that, assuming mathsfP neq mathsfNP, for any ε>0, no polynomial-time algorithm can approximate fair k-center to (3-ε)-factor. Our inapproximability results hold even when only two disjoint groups are present and at least one center must be chosen from each group. Further, it extends to the canonical one-per-group setting with k-groups (for arbitrary k), where exactly one center must be selected from each group. Consequently, the factor-3 barrier for fair k-center in general metric spaces is inherent, and existing 3-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the k-supplier formulation, where both the unconstrained and fair variants admit factor-3 approximation in polynomial time.