Timezone: »

 
Poster
Individual Fairness for k-Clustering
Sepideh Mahabadi · Ali Vakilian

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @ Virtual
in Poster Session 1 »
We give a local search based algorithm for $k$-median and $k$-means (and more generally for any $k$-clustering with $\ell_p$ norm cost function) from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. An individually fair clustering provides such a guarantee for every point $x\in P$. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible $k$-clustering with respect to this fairness condition. In this work, we show how to get an approximately \emph{optimal} such fair $k$-clustering. The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor).
Keywords: Clustering · Combinatorial Optimization · Unsupervised and Semi-supervised Learning · Fairness, Equity and Justice
[ Slides] 

Author Information

Sepideh Mahabadi (Toyota Technological Institute at Chicago)
Ali Vakilian (University of Wisconsin-Madison)

More from the Same Authors