On the Hardness of Approximation of the Fair k-Center Problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910028712116224 |
|---|---|
| author | Thejaswi, Suhas |
| author_facet | Thejaswi, Suhas |
| contents | 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 $\mathsf{P} \neq \mathsf{NP}$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16688 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Hardness of Approximation of the Fair k-Center Problem Thejaswi, Suhas Computational Complexity Data Structures and Algorithms Machine Learning 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 $\mathsf{P} \neq \mathsf{NP}$, 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. |
| title | On the Hardness of Approximation of the Fair k-Center Problem |
| topic | Computational Complexity Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2602.16688 |