Individual Fairness for k-Clustering

@InProceedings{pmlr-v119-mahabadi20a,
  title = 	 {Individual Fairness for k-Clustering},
  author =       {Mahabadi, Sepideh and Vakilian, Ali},
  booktitle = 	 {Proceedings of the 37th International Conference on Machine Learning},
  pages = 	 {6586--6596},
  year = 	 {2020},
  editor = 	 {III, Hal Daumé and Singh, Aarti},
  volume = 	 {119},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {13--18 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v119/mahabadi20a/mahabadi20a.pdf},
  url = 	 {https://proceedings.mlr.press/v119/mahabadi20a.html},
  abstract = 	 {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)$. In this work, we show how to get an approximately 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).}
}