Corvinus
Corvinus

Optimal partisan districting on planar geographies

Tasnádi, Attila (2013) Optimal partisan districting on planar geographies. Working Paper. Corvinus University of Budapest. (Unpublished)

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
207kB

Abstract

We show that optimal partisan districting in the plane with geographical constraints is an NP-complete problem.

Item Type:Monograph (Working Paper)
Uncontrolled Keywords:districting, gerrymandering, NP-complete problems
Divisions:Faculty of Economics > Department of Mathematics
Subjects:Mathematics, Econometrics
Political science
Computer science
Projects:MTA-BCE "Lendület" Stratégiai Interakciók Kutatócsoport
References:

M. Altman, Is automation the answer? The computational complexity of automated redistricting, Rutgers Computer and Law Technology Journal 23 (1997) 81-142.

M. Altman, M. McDonald, The promise and perils of computers in redistricting, Duke Constitutional Law and Policy Journal 5 (2010) 69-112.

F. Bacao, V. Lobo, M. Painho, Applying genetic algorithms to zone design, Soft Computing 9 (2005) 341-348.

B. Bozkaya, E. Erkut, G. Laporte, A tabu search heuristic and adaptive memory procedure for political districting, European Journal of Operational Research 144 (2003) 12-26.

J.E. Burns, The maximum independent set problem for cubic planar graphs, Networks 19 (1989) 373-378.

C-I. Chou, S.P. Li, Taming the gerrymander--statistical physics approach to political districting problem, Physica A 369 (2006) 799-808.

E. Choukhmane, J. Franco, An approximation algorithm for the maximum independent set problem in cubic planar graphs, Networks 16 (1986) 349-356.

M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H Freeman and Company, San Francisco, 1979.

R.S. Garfinkel, G.L. Nemhauser, Optimal political districting by implicit enumeration techniques, Management Science 16 (1970) 495-508.

S.W. Hess, J.B Weaver, H.J. Siegfeldt, J.N. Whelan, P.A. Zitlau, Nonpartisan political redistricting by computer, Operations Research 13 (1965) 998-1006.

B. Keszegh, J. Pach, D. Pálvölgyi, G. Tóth, Drawing cubic graphs with at most five slopes, Computational Geometry 40 (2008) 138-147.

Y. Liu, P. Marchioro, R. Petreschi, At most single-bend embeddings of cubic graphs, Applied Mathematics - A Journal of Chinese Universities 9 (1994) 127-142.

A. Mehrotra, E.L. Johnson, G.L. Nemhauser, An optimization based heuristic for political districting, Management Science 44 (1998) 1100-1114.

S.S. Nagel, Computers & the law & politics of redistricting, Polity 5 (1972) 77-93.

C. Puppe, A. Tasnádi, Optimal redistricting under geographical constraints: Why 'pack and crack' does not work, Economics Letters 105 (2009) 93-96.

F. Ricca, B. Simeone, Local search algorithms for political districting, European Journal of Operational Research 189 (2008) 1409-1426.

F. Ricca, A. Scozzari, B. Simeone, Weighted Vornoi region algorithms for political districting, Mathematical Computer Modelling 48 (2008) 1468-1477.

F. Ricca, A. Scozzari, B. Simeone, Political districting: from classical models to recent approaches, 4OR (2011) 223-254.

A. Tasnádi, The political districting problem: a survey, Society and Economy 33 (2011) 543-553.

W. Vickrey, On the prevention of gerrymandering, Political Science Quarterly 76 (1961) 105-110.

ID Code:1282
Deposited By: Attila Tasnádi
Deposited On:01 Jul 2013 13:34
Last Modified:01 Jul 2013 13:36

Repository Staff Only: item control page

Downloads

Downloads per month over past year

View more statistics