Arturs Backurs,
Piotr Indyk,
Krzysztof Onak,
Baruch Schieber,
Ali Vakilian,
Tal Wagner
;
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:405-413, 2019.
Abstract
We study the fair variant of the classic k-median 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 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.
@InProceedings{pmlr-v97-backurs19a,
title = {Scalable Fair Clustering},
author = {Backurs, Arturs and Indyk, Piotr and Onak, Krzysztof and Schieber, Baruch and Vakilian, Ali and Wagner, Tal},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {405--413},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
address = {Long Beach, California, USA},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/backurs19a/backurs19a.pdf},
url = {http://proceedings.mlr.press/v97/backurs19a.html},
abstract = {We study the fair variant of the classic k-median 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 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.}
}
%0 Conference Paper
%T Scalable Fair Clustering
%A Arturs Backurs
%A Piotr Indyk
%A Krzysztof Onak
%A Baruch Schieber
%A Ali Vakilian
%A Tal Wagner
%B Proceedings of the 36th International Conference on Machine Learning
%C Proceedings of Machine Learning Research
%D 2019
%E Kamalika Chaudhuri
%E Ruslan Salakhutdinov
%F pmlr-v97-backurs19a
%I PMLR
%J Proceedings of Machine Learning Research
%P 405--413
%U http://proceedings.mlr.press
%V 97
%W PMLR
%X We study the fair variant of the classic k-median 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 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.
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A. & Wagner, T.. (2019). Scalable Fair Clustering. Proceedings of the 36th International Conference on Machine Learning, in PMLR 97:405-413
This site last compiled Mon, 16 Sep 2019 16:05:04 +0000