Search papers, labs, and topics across Lattice.
This paper introduces a novel class of algorithms, termed "Bonsai," for independently sampling graph partitions, specifically targeting the generation of ensembles of district plans. The algorithms leverage a carefully designed probability distribution over graph partitions, enabling efficient and independent sampling. Experiments on grid graphs and state congressional/legislative maps demonstrate that Bonsai algorithms perform competitively with standard Markov Chain Monte Carlo methods.
Independent sampling of graph partitions is now a practical alternative to MCMC, offering a new path for generating diverse redistricting plans.
We develop effective methods for constructing an ensemble of district plans via independent sampling from a reasonable probability distribution on the space of graph partitions. We compare the performance of our algorithms to that of standard Markov Chain based algorithms in the context of grid graphs and state congressional and legislative maps. For the case of perfect population balance between districts, we provide an explicit description of the distribution from which our method samples.
