EL-Clustering: Combining Upper- and Lower-Bounded Clusterings for Equitable Load Constraints

Abstract

The application of an ordinary clustering algorithm may yield a clustering output where the number of points per cluster (cluster size) varies significantly. In settings where the centers correspond to facilities that provide a service, this can be highly undesirable as the cluster size is essentially the service load for a facility. While prior work has considered imposing either a lower bound on the cluster sizes or an upper bound, imposing both bounds simultaneously has seen limited work, especially for the $k$-median objective, despite its strong practical motivation. In this paper, we solve the \emph{equitable load} (\EL{}) clustering problem where we minimize the $k$-median objective subject to the cluster sizes not exceeding an upper bound or falling below a lower bound. We solve this problem using a modular approach. Specifically, given a clustering solution that satisfies the lower bound constraints and another that satisfies the upper bound constraints, we introduce a combination algorithm which essentially combines both solutions to produce one that satisfies both constraints simultaneously at the expense of a bounded degradation in the $k$-median objective and a slight violation of the upper bound. Our combination algorithm runs in $O(k^3+n)$ time, where $n$ is the number of points and is faster than standard $k$-median algorithms that satisfy either the lower or upper bound constraints. Interestingly, our results can be generalized to various other clustering objectives, including the $k$-means objective. We also do empirical evaluation for $k$-Median objective on benchmark datasets to show that both, the cost as well as the violation factor are significantly smaller in practice than the theoretical worst-case guarantees\footnote{https://github.com/0-rudra-0/el-clustering}.