Skip to yearly menu bar Skip to main content


Poster

Parameterized Approximation Schemes for Fair-Range Clustering

Zhen Zhang · Xiaohong Chen · Limei Liu · Jie Chen · Junyu Huang · Qilong Feng

[ ]
Wed 11 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: 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 parameterized approximation ratios of $1+2e^{-1}+\varepsilon$ for fair-range $k$-median and $1+8e^{-1}+\varepsilon$ for fair-range $k$-means obtained in a simpler case considering only the lower bound constraint.

Live content is unavailable. Log in and register to view live content