Paper ID: | 2750 |
---|---|

Title: | Fair Algorithms for Clustering |

The paper is interesting, well-written and addresses an important topic. Its main contributions are described in the section above. This paper is original in addressing a generalization of previously considered fair clustering cases (one of them published in NIPS 2017). As mentioned above, the authors note that a similar generalization was considered in a parallel work (currently available on Arxiv). While the main LP-based algorithm is relatively simple and uses quite standard methods (effectively MBDMB), it is not trivial, and these methods are used for this problem in a nice way. The experimental results are also interesting, but using just 4 UCI datasets for studying this general problem seems too little, and might not reflect the overall behavior. It is unclear, for example, why the authors did not use the Diabetes dataset used in the NIPS 2017 paper of Chierichetti et al that they cite. The main significance of the paper is in the theoretical result, which significantly improves upon previous work, while the experiments mainly explore sample cases and demonstrate that they may behave better than guaranteed. I am currently grading this paper as a good submission. For accepting it following the authors response, I expect to at least see experimental results for the missing dataset out of the datasets considered in the NIPS2017 paper (UCI Diabetes).

The paper studies fair variants of a class of clustering problems that include k-center, k-median, and k-means. The fairness constraint studied here is a generalization of the one introduced by Chierchietti et al. The main result is a black-box reduction of the fair clustering problem to the vanilla clustering problem. This is an interesting result, and immediately gives constant-factor approximation algorithms (with constant violation of the fairness constraint) for the corresponding fair clustering problems. The experimental results are not impressive. Mainly, the fair algorithm given in the paper is compared with the vanilla solution. No comparison with a baseline is provided. Also, the paper does not discuss a recent related paper by Ahmadian et al. (in KDD 2019). The two papers have some overlap in the results and the techniques. Even though the overlap doesn't cover the main result of the present paper (the black-box reduction), it still needs to be discussed.

The paper gives a new algorithm for a generalized version of the fair clustering problem. The algorithm works by using a black-box clustering algorithm and then reassigning points in order to meet the fairness constraints. The point reassignment algorithm is an LP relaxation solved via iterative rounding. The reduction and black-box setup of the algorithm is elegant and nicely simple. Because of the black-box clustering algorithm setup, this solution applies to k-means, k-median, and k-center algorithms.