NeurIPS 2020

KFC: A Scalable Approximation Algorithm for $k$−center Fair Clustering

Meta Review

The paper presents a speed-up of a known fair k-center/k-supplier algorithm alongside an improved approximation guarantee (4->3) for the k-center case. The latter is quite nice since there is also a lower bound of 3 for the fair (assignment) k-center problem. The authors missed the paper that contains this lower bound (Bercea et al). It is still is not tight since the proposed algorithms have a fairness violation and the lower bound is for the assignment problem, but it still seems close to the best achievable bound. However, the main contribution is the LP size reduction and resulting practical speed-up, which is demonstrated in experiments. The techniques are not surprisingly novel.