On the Complexity of Sampling Redistricting Plans
Not on the map. Why?
Abstract (arXiv)
A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of mathbbZ2. We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 10 Jun 2022.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2025: 1.
1 paper.