Autor:	Charikar, Moses, Liu, Paul, Liu, Tianyu, Vuong, Thuy-Duong
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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 $\mathbb{Z}_2.$ We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling. Comment: Correcting the definition of Markov chain to sample from spanning tree distribution
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2206.04883 Zobrazit plný text záznamu View this record from Arxiv