New Coresets for Fair Clustering

We construct the first coreset of size near-linear in $k$ for fair \kMedian in general metric spaces. Combined with the standard merge-and-reduce framework, our construction also gives the first streaming algorithm for fair \kMedian with space complexity near-linear in $k$. The main technical innovation is a distributional reinterpretation of capacitated clustering that the cost of assigning a dataset to a capacitated center set can be expressed as the earth mover's distance between two discrete distributions. This viewpoint enables us to use tools from optimal transport to analyse uniform sampling. A key ingredient in this analysis is a new family of problem-specific $\eps$-nets for the earth mover's distance.