Tasnádi, Attila (2013) Optimal partisan districting on planar geographies. Working Paper. Corvinus University of Budapest. (Unpublished)
|
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
Download Statistics
Download Statistics