Timezone: »

 
Poster
Approximation Algorithms for Fair Range Clustering
Sedjro Salomon Hotegni · Sepideh Mahabadi · Ali Vakilian

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #335
in Poster Session 1 »
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_{v\in P} d(v,C)^p)^{1/p}$) such that for each group $i\in \ell$, $|C\cap 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 an efficient constant factor approximation algorithm for the fair range $\ell_p$-clustering for all values of $p\in [1,\infty)$.
[ Slides]  [ PDF]  [ Poster] 

Author Information

Sedjro Salomon Hotegni (Universität Paderborn)
Sepideh Mahabadi (Toyota Technological Institute at Chicago)
Ali Vakilian (Toyota Technological Institute at Chicago)

More from the Same Authors