We have recently posted a pre-print of a Multi-Scale Merge-Split sampling algorithm. The work’s central contribution is to provide a multi-scale representation of the state space which can be used to efficiently sample redistricting plans containing both fine and coarse-scale details. Because of the coarse-graining, this algorithm promises fast scaling on problems with fine-scale graphs. It also is capable of naturally preserving nested communities of interest (such as precincts made up of census blocks, and counties made up of precincts) without creating prohibitive energetic barriers which slow mixing. This work builds on our Merge-Split algorithm, which, in turn, builds on the ReCom algorithm.
