@inproceedings{
zhang2024parameterized,
title={Parameterized Approximation Schemes for Fair-Range Clustering},
author={Zhen Zhang and Xiaohong Chen and Limei Liu and Jie Chen and Junyu Huang and Qilong Feng},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=ZzgbUDspzJ}
}
Fair-range clustering extends classical clustering formulations by associating each data point with one or several demographic labels. It imposes lower and upper bound constraints on the number of opened facilities associated with each label, ensuring fair representation of all demographic groups by the opened 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).
Parameterized Approximation Schemes for Fair-Range Clustering
Zhen Zhang Xiaohong Chen Limei Liu Jie Chen Junyu Huang Qilong Feng