Doubly Constrained Fair Clustering for General p-Norms
摘要
Fairness in clustering has received significant attention. Dickerson et al. in 2023 first proposed the doubly constrained fair clustering problem that aims two fairness constraints, namely, (1) the Group Fairness (GF), which requires that different groups within each cluster have a certain degree of representation, and (2) the Diversity in Center Selection fairness (DS), which requires that the selected centers represent a diverse range of different groups. However, their algorithm only focuses on the k-center objective. In this paper, we generalize the doubly constrained fair clustering to \(\ell _p\) norm objectives with general p, thus including k-Center, k-Median, and k-Means as special cases. We propose the first approximation algorithm for the doubly constrained fair clustering problem with general p-norms. In polynomial time, our algorithm finds an \(O(\Delta ^{\frac{1}{p}})\) -approximate clustering that violates the GF constraint by an additive factor of 5 and satisfies the DS constraint, where \(\Delta \) is the largest size of clusters in the solution. Our main contribution is a novel method to select centers using the min cost network flow approach. Finally, we conduct experiments to validate our algorithm. The experimental results show that the clustering cost of our algorithm, while simultaneously considering both of the GF and DS constraints, is nearly identical to that of the clustering algorithm which only considers the GF constraint.