[edit]
Improved Approximation Algorithms for Individually Fair Clustering
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:8758-8779, 2022.
Abstract
We consider the k-clustering problem with ℓp-norm cost, which includes k-median, k-means and k-center, under an individual notion of fairness proposed by Jung et al. [2020]: given a set of points P of size n, a set of k centers induces a fair clustering if every point in P has a center among its n/k closest neighbors. Mahabadi and Vakilian [2020] presented a (pO(p),7)-bicriteria approximation for fair clustering with ℓp-norm cost: every point finds a center within distance at most 7 times its distance to its (n/k)-th closest neighbor and the ℓp-norm cost of the solution is at most pO(p) times the cost of an optimal fair solution. In this work, for any ϵ>0, we present an improved (16p+ϵ,3)-bicriteria for this problem. Moreover, for p=1 (k-median) and p=∞ (k-center), we present improved cost-approximation factors 7.081+ϵ and 3+ϵ respectively. To achieve our guarantees, we extend the framework of [Charikar et al.,2002, Swamy, 2016] and devise a 16p-approximation algorithm for the facility location with ℓp-norm cost under matroid constraint which might be of an independent interest. Besides, our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement proposed by [Kleindessner et al. 2019], which is essentially the median matroid problem.