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 = P1 uplus P2 uplus cdots uplus Pℓ) and a set of ℓ intervals [α1, β1], cdots, [αℓ, βℓ] 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., (sumv∈ P d(v,C)p)1/p) such that for each group i∈ ℓ, |Ccap Pi| ∈ [α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,∞).