Approximation Algorithms for Fair Range Clustering

This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick k centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of n points in a metric space (P,d) where each point belongs to one of the ℓ different demographics (i.e., P=P_1⊎P_2⊎⋯⊎P_ℓ) and a set of ℓ intervals [α_1,β_1],⋯,[α_ℓ,β_ℓ] on desired number of centers from each group, the goal is to pick a set of k centers C with minimum ℓ_p-clustering cost (i.e., (∑_{v∈P}d(v,C)^p)^{1/p}) such that for each group i∈ℓ, |C∩P_i|∈[α_i,β_i]. In particular, the fair range ℓ_p-clustering captures fair range k-center, k-median and k-means as its special cases. In this work, we provide efficient constant factor approximation algorithms for fair range ℓ_p-clustering for all values of p∈[1,∞).$