Papers › Individual Fairness for k-Clustering
Individual Fairness for k-Clustering
Sepideh Mahabadi, Ali Vakilian
We give a local search based algorithm for k-median and k-means (and more generally for any k-clustering with ℓₚ 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 [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 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections