My caption 😄

Scalable Approximations of Capacitated k-medians for Political Districting


We present a novel approach for efficiently finding high quality solutions to the uniformly capacitated $k$-medians problem (UCKMP) with optimality bounds for political districting. Our approach is to solve the LP relaxation to construct a weighted bipartite graph with weight equal to the value of the associated LP variable. This bipartite graph is used as the input for a spectral partitioning subroutine which picks the final $k$ centers. These centers are then used in a transportation problem to do the final assignment of census tracts to centers in polynomial time. Our approach is scalable because the most costly part of our algorithm, solving the relaxation, is highly parallelizable and because the tracts exist in (near) euclidean space, there are a number of natural variable pruning heuristics that greatly cut down the total number of variables without affecting solution quality. We present an extensive empirical analysis of using our approach to create congressional districts for American states our of census tracts.

Technical Report