Parameterized Approximation Schemes for Fair Clustering in Doubling Metrics

摘要

Fair clustering has garnered considerable attention, with various fairness notions proposed to ensure equitable representation across demographic groups. In this paper, we focus on the k-center problem in bounded doubling metrics under two popular fairness requirements: group fairness and data summarization fairness, referred to Group Fair k-Center (Gf-k-Cen) and Data Summarization Fair k-Center (Dsf-k-Cen), respectively. Both fairness notions extend classical clustering formulation by associating each data point with a demographic label. Motivated by recent advances in parameterized approximation results for fair clustering, we investigate whether these problems admit Fixed-Parameter Tractable (FPT) approximation schemes in bounded doubling metrics. The previous algorithms typically neglect the local structural properties induced by fairness constraints itself, which limits their approximation quality. By further leveraging the geometric properties of doubling metrics together with local fairness information, we develop a candidate-based structural method that yields (1+eps)-approximation algorithms with FPT running times for both problems, parameterized by the number of selected centers. To the best of our knowledge, these results constitute the first parameterized approximation schemes for the Gf-k-Cen and Dsf-k-Cen problems in bounded doubling metrics.