Parameterized Approximation Schemes for Fair-Range Clustering

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).

Authors

• Zhen Zhang Shenzhen MSU-BIT University
• Xiaohong Chen East China Normal University
• Limei Liu Hunan University of Technology and Business Xiangjiang Laboratory
• Jie Chen
• Junyu Huang School of Computer Science and Engineering, Central South University, Changsha 410083, China Xiangjiang Laboratory, Changsha 410205, China
• Qilong Feng School of Computer Science and Engineering, Central South University, Changsha 410083, China Xiangjiang Laboratory, Changsha 410205, China

Keywords

No keywords are indexed for this paper.