[Paper] On the Hardness of Approximation of the Fair k-Center Problem

Source: arXiv - 2602.16688v1

Overview

The paper tackles a fundamental clustering task—fair k‑center—where data points belong to pre‑defined groups (e.g., demographic slices) and the algorithm must pick a fixed number of “centers” from each group. While a 3‑approximation algorithm is known, it was unclear whether this bound could be improved. The author proves that any improvement below a factor of 3 would be NP‑hard, even in the simplest two‑group setting, establishing the 3‑approximation as essentially optimal.

Key Contributions

• Tight hardness result: Achieving a ((3-\varepsilon))-approximation for any (\varepsilon>0) is NP‑hard (assuming P ≠ NP).
• Minimal setting suffices: The hardness holds with just two disjoint groups and the requirement that each group contributes at least one center.
• One‑per‑group extension: Extends the result to the “one‑center‑per‑group” variant with an arbitrary number of groups (k).
• Contrast with related problems: The analogous k‑supplier problem admits a 3‑approximation even in the fair setting, underscoring a sharp complexity gap.
• Implication for existing algorithms: Confirms that the best known polynomial‑time 3‑approximation algorithms are optimal up to lower‑order terms.

Methodology

The proof follows a classic gap‑introducing reduction from a known NP‑hard problem (e.g., a variant of 3‑SAT or a label‑cover instance). The construction creates a metric space where:

1. Clusters correspond to logical variables or clauses and are split into two groups.
2. Distances are carefully calibrated so that any solution respecting the fairness constraints must either achieve a radius close to the optimal value (the “yes” case) or be forced to incur at least three times that radius (the “no” case).
3. By showing that distinguishing these two cases would solve the underlying NP‑hard problem, the author establishes the ((3-\varepsilon)) inapproximability.

The reduction works even when each group must contribute exactly one center, simplifying the argument and strengthening the result.

Results & Findings

• Hardness threshold: No polynomial‑time algorithm can guarantee a factor better than 3 for fair k‑center unless P = NP.
• Robustness: The hardness persists under very restrictive fairness models (two groups, one‑per‑group).
• Optimality of current algorithms: Existing 3‑approximation methods (e.g., greedy clustering with fairness checks) are essentially the best we can hope for in general metrics.
• Differentiation from k‑supplier: While fair k‑center hits the 3 barrier, fair k‑supplier remains at the same approximation factor for both constrained and unconstrained versions, indicating that the difficulty lies in the “center‑selection” requirement rather than the “supplier” formulation.

Practical Implications

• Algorithm selection: Practitioners can confidently use the current 3‑approximation algorithms for fair clustering, knowing they are near‑optimal in worst‑case scenarios.
• Expectation management: Product teams building fairness‑aware services (e.g., location‑based recommendations, facility placement with demographic quotas) should not expect algorithms that consistently beat the 3× radius bound without sacrificing polynomial runtime.
• Metric design: Since the hardness holds for any metric, developers might explore problem‑specific metrics (e.g., embedding data into low‑dimensional Euclidean space) where heuristic improvements could be observed in practice, even if worst‑case guarantees stay at 3.
• Hybrid approaches: The result encourages combining the 3‑approximation core with post‑processing or local search to improve average‑case performance while accepting that the theoretical bound cannot be lowered.
• Benchmarking: Researchers and engineers can use the paper’s constructions as stress tests for new fair clustering heuristics, ensuring they handle the hardest instances.

Limitations & Future Work

• Worst‑case focus: The hardness proof is existential; many real‑world datasets may admit better‑than‑3 approximations in practice.
• Metric assumptions: The result applies to general metrics; specialized metrics (e.g., tree metrics, planar graphs) might admit tighter approximations, a direction left open.
• Beyond approximation: The paper does not address parameterized or fixed‑parameter tractable algorithms that could be efficient for small numbers of groups or centers.
• Algorithmic extensions: Future work could explore bicriteria relaxations (allowing slight violations of group quotas) or smoothed analysis to understand typical‑case behavior.

Bottom line: If you need a fairness‑aware clustering routine that respects group quotas, the 3‑approximation algorithms you already have are essentially as good as it gets—unless you’re willing to trade optimality for speed, relax the fairness constraints, or restrict the problem to special metric spaces.

Authors

• Suhas Thejaswi

Paper Information

• arXiv ID: 2602.16688v1
• Categories: cs.CC, cs.DS, cs.LG
• Published: February 18, 2026
• PDF: Download PDF