Efficient Algorithms For Fair Clustering with a New Fairness Notion
  We revisit the problem of fair clustering, first introduced by Chierichetti
et al., that requires each protected attribute to have approximately equal
representation in every cluster; i.e., a balance property. Existing solutions
to fair clustering are either not scalable or do not achieve an optimal
trade-off between clustering objective and fairness. In this paper, we propose
a new notion of fairness, which we call $tau$-fair fairness, that strictly
generalizes the balance property and enables a fine-grained efficiency vs.
fairness trade-off. Furthermore, we show that simple greedy round-robin based
algorithms achieve this trade-off efficiently. Under a more general setting of
multi-valued protected attributes, we rigorously analyze the theoretical
properties of the our algorithms. Our experimental results suggest that the
proposed solution outperforms all the state-of-the-art algorithms and works
exceptionally well even for a large number of clusters.
