Optimal partisan districting on planar geographies

Fleiner, Balázs, Nagy, Balázs and Tasnádi, Attila (2017) Optimal partisan districting on planar geographies. Central European Journal of Operations Research, 25 (4). pp. 879-888. DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:

open access


We show that optimal partisan districting and majority securing districting in the plane with geographical constraints are NP-complete problems. We provide a polynomial time algorithm for determining an optimal partisan districting for a simplified version of the problem. In addition, we give possible explanations for why finding an optimal partisan districting for real-life problems cannot be guaranteed.

Item Type:Article
Uncontrolled Keywords:computational complexity, dynamic programming, polyominoes, pack and crack, gerrymandering
Subjects:Mathematics, Econometrics
Projects:OTKA K-112975
ID Code:6378
Deposited By: MTMT SWORD
Deposited On:19 Mar 2021 09:41
Last Modified:19 Mar 2021 12:59

Repository Staff Only: item control page


Downloads per month over past year

View more statistics