Scalable Fair Clustering
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:405413, 2019.
Abstract
We study the fair variant of the classic kmedian problem introduced by (Chierichetti et al., NeurIPS 2017) in which the points are colored, and the goal is to minimize the same average distance objective as in the standard $k$median problem while ensuring that all clusters have an “approximately equal” number of points of each color. (Chierichetti et al., NeurIPS 2017) proposed a twophase algorithm for fair $k$clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the kmedian objective. In the second step, fairlets are merged into k clusters by one of the existing kmedian algorithms. The running time of this algorithm is dominated by the first step, which takes superquadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.
Related Material


