On the Hardness of Approximation of the Fair k-Center Problem
2026-02-18 • Computational Complexity
Computational ComplexityData Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study a version of the k-center problem where data points are divided into groups, and a certain number of centers must be picked from each group to cover all points. They prove that it is very hard (NP-hard) to do better than a 3-approximation for this fair k-center problem, meaning you can't generally find a solution closer than 3 times the optimal maximum distance. This hardness holds even with just two groups or when picking exactly one center per group. Their results show that existing algorithms that achieve a 3-approximation are as good as possible unless P=NP. This differs from a related problem called k-supplier, where a similar approximation factor is achievable more easily.
k-center problemfair clusteringapproximation algorithmsNP-hardnessmetric spacesapproximation ratioP vs NPdisjoint groupsk-supplier problem
Authors
Suhas Thejaswi
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 $ε>0$, achieving a $(3-ε)$-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$-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.