TY - GEN

T1 - Scalable fair clustering

AU - Backurs, Arturs

AU - Indyk, Piotr

AU - Onak, Krzysztof

AU - Schieber, Baruch

AU - Vakilian, A. H.

AU - Wagner, Tal

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We study the fair variant of the classic k-median problem introduced by Chierichetti et al. (Chierichetti et al., 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. proposed a two-phase 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 k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

AB - We study the fair variant of the classic k-median problem introduced by Chierichetti et al. (Chierichetti et al., 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. proposed a two-phase 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 k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

UR - http://www.scopus.com/inward/record.url?scp=85071184851&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071184851&partnerID=8YFLogxK

M3 - Conference contribution

T3 - 36th International Conference on Machine Learning, ICML 2019

SP - 623

EP - 634

BT - 36th International Conference on Machine Learning, ICML 2019

PB - International Machine Learning Society (IMLS)

T2 - 36th International Conference on Machine Learning, ICML 2019

Y2 - 9 June 2019 through 15 June 2019

ER -