![[2602.16688] On the Hardness of Approximation of the Fair k-Center Problem](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.16688] On the Hardness of Approximation of the Fair k-Center Problem
Summary
This paper addresses the NP-hardness of approximating the fair k-center problem, proving that achieving a (3-ε)-approximation is impossible under standard complexity assumptions.
Why It Matters
Understanding the limitations of approximation algorithms for the fair k-center problem is crucial for fields like machine learning and data science, where equitable data representation is essential. This research clarifies the boundaries of what can be achieved algorithmically, informing future work in optimization and computational complexity.
Key Takeaways
- The fair k-center problem's (3-ε)-approximation is NP-hard.
- Existing 3-approximation algorithms are optimal under current complexity assumptions.
- The results apply even in restricted settings with two groups or more.
- This work contrasts with the k-supplier problem, which allows for polynomial-time approximations.
- The findings have implications for equitable data center selection in various applications.
Computer Science > Computational Complexity arXiv:2602.16688 (cs) [Submitted on 18 Feb 2026] Title:On the Hardness of Approximation of the Fair k-Center Problem Authors:Suhas Thejaswi View a PDF of the paper titled On the Hardness of Approximation of the Fair k-Center Problem, by Suhas Thejaswi View PDF HTML (experimental) Abstract:In this work, we study the hardness of approximation of the fair $k$-center problem. Here the data points are partitioned into groups and the task is to choose a prescribed number of data points from each group, called centers, while minimizing the maximum distance from any point to its closest center. Although a polynomial-time $3$-approximation is known for this problem in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the unconstrained $k$-center problem admits a polynomial-time factor-$2$ approximation. We resolve this open question by proving that, for every $\epsilon>0$, achieving a $(3-\epsilon)$-approximation is NP-hard, assuming $\text{P} \neq \text{NP}$. 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$-a...
