Individual Fairness for k-Clustering

We give a local search based algorithm for k-median and k-means (and more generally for any k-clustering with 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 ∈ P expects to have a center within radius r(x). An individually fair clustering provides such a guarantee for every point x ∈ P . This notion of fairness was introduced in [JKL19] 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 a bicriteria approximation for 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). Further, we complement our theoretical bounds with empirical evaluation.