Approximation Algorithms for Fair Range Clustering. (arXiv:2306.06778v2 [cs.LG] UPDATED)

Approximation Algorithms for Fair Range Clustering. (arXiv:2306.06778v2 [cs.LG] UPDATED)
By: <a href="">S&#xe8;djro S. Hotegni</a>, <a href="">Sepideh Mahabadi</a>, <a href="">Ali Vakilian</a> Posted: June 23, 2023

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 $ell$ different demographics (i.e., $P = P_1 uplus P_2
uplus cdots uplus P_ell$) and a set of $ell$ intervals $[alpha_1,
beta_1], cdots, [alpha_ell, beta_ell]$ on desired number of centers from
each group, the goal is to pick a set of $k$ centers $C$ with minimum
$ell_p$-clustering cost (i.e., $(sum_{vin P} d(v,C)^p)^{1/p}$) such that for
each group $iin ell$, $|Ccap P_i| in [alpha_i, beta_i]$. In particular,
the fair range $ell_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 $ell_p$-clustering for all
values of $pin [1,infty)$.

Provided by:



Moderator and Editor