Fast and Accurate Fair k-Center Clustering in Doubling Metrics

We study the classic k-center clustering problem under the additional constraint that each cluster should be fair. In this setting, each point is marked with one or more colors, which can be used to model protected attributes (e.g., gender or ethnicity). A cluster is deemed fair if, for every color, the fraction of its points marked with that color is within some prespecified range. We present a coreset-based approach to fair k-center clustering for general metric spaces which attains almost the best approximation quality of the current state of the art solutions, while featuring running times which can be orders of magnitude faster for large datasets of low doubling dimension. We devise sequential, streaming and MapReduce implementations of our approach and conduct a thorough experimental analysis to provide evidence of their practicality, scalability, and effectiveness.