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

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.