Parameterized Approximation Schemes for Fair-Range Clustering
Hunan University of Technology and Business · Central South University · Hunan University Of Technology and Business · Hunan University · Central South University, China, Tsinghua University · Central South University, China
PDF 由论文原始站点提供，PaperCompass 不保存论文文件。
摘要
Fair-range clustering extends classical clustering formulations by associating each data point with one or more demographic labels. It imposes lower and upper bound constraints on the number of facilities opened for each label, ensuring fair representation of all demographic groups by the selected facilities. In this paper we focus on the fair-range $k$-median and $k$-means problems in Euclidean spaces. We give $(1+\varepsilon)$-approximation algorithms with fixed-parameter tractable running times for both problems, parameterized by the numbers of opened facilities and demographic labels. For Euclidean metrics, these are the first parameterized approximation schemes for the problems, improving upon the previously known $O(1)$-approximation ratios given by Thejaswi et al. (KDD 2022).