Coresets for Capacitated Clustering via Dual Concentration

Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam, Erik Waingarten

We study coresets for clustering problems, focusing on the classical $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in $k$ while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset…