arXiv:2602.16688cs.CCcs.DS2026-02

证明了公平k中心问题无法突破3倍近似下界,算法已最优。

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

  • 通过归约证明任意多项式算法难以优于3倍近似。
  • 即使只有两个组且每组至少选一个中心,仍无法改进至3-ε。
  • 适用于关注公平性约束下算法极限的研究者。

本文研究公平k中心问题的近似难度。给定度量空间中按组划分的数据点,需选出k个中心,使每组至少满足指定数量的数据点被覆盖,同时最小化任意点到最近中心的最大距离。尽管已知存在多项式时间3-近似算法,但该比值是否可改进仍悬而未决,尤其因经典无约束k中心问题可实现2-近似。本文证明:在P≠NP假设下,对任意ε>0,不存在多项式时间算法能将公平k中心问题近似至(3−ε)因子。该下界在仅含两个互不相交组且每组至少选一个中心的情况下依然成立,并扩展至每组恰好选一个中心的典型情形(任意数量群体)。因此,一般度量空间中公平k中心问题的3倍近似界限是固有的,现有3-近似算法在这些受限场景下已为最优(忽略低阶项)。此结果与k供应者模型形成鲜明对比,后者无论有无公平约束均存在3-近似多项式算法。

原文摘要 · Abstract (English)

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.

近似算法公平性组合优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。