@inproceedings{hotegni2023approximation,
author = {Hotegni, Sèdjro S. and Mahabadi, Sepideh and Vakilian, Ali},
title = {Approximation Algorithms for Fair Range Clustering},
booktitle = {ICML},
year = {2023},
month = {July},
abstract = {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,∞).$},
url = {http://approjects.co.za/?big=en-us/research/publication/approximation-algorithms-for-fair-range-clustering/},
}