Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân vùng đảng phái tối ưu trên các khu vực địa lý phẳng
Tóm tắt
Chúng tôi chỉ ra rằng phân vùng đảng phái tối ưu và phân vùng đảm bảo đa số trong không gian hai chiều với các ràng buộc địa lý là những bài toán NP-đầy đủ. Chúng tôi cung cấp một thuật toán thời gian đa thức để xác định phân vùng đảng phái tối ưu cho một phiên bản đơn giản của bài toán. Ngoài ra, chúng tôi đưa ra những giải thích có thể cho lý do tại sao không thể đảm bảo việc tìm kiếm một phân vùng đảng phái tối ưu cho các vấn đề trong thực tế.
Từ khóa
#phân vùng đảng phái #thuật toán #bài toán NP-đầy đủ #đa số #ràng buộc địa lýTài liệu tham khảo
Altman M (1997) Is automation the answer? the computational complexity of automated redistricting. Rutgers Comput Law Technol J 23:81–142
Altman M, McDonald M (2010) The promise and perils of computers in redistricting. Duke J Const L & Pub Pol’y 5:69–112
Bação F, Lobo V, Painho M (2005) Applying genetic algorithms to zone design. Soft Comput 9:341–348
Bozkaya B, Erkut E, Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur J Oper Res 144:12–26
Chou C-I, Li SP (2006) Taming the gerrymander-statistical physics approach to political districting problem. Phys A 369:799–808
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, San Francisco
Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Manag Sci 16:495–508
Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Nonpartisan political redistricting by computer. Oper Res 13:998–1006
Jensen I (2003) Counting polyominoes: a parallel implementation for cluster computing. In: Proceedings of the international conference on computational science, part III. (Lecture notes in computer science), vol 2659. Springer, Melbourne, pp 203–212
Kalcsics J (2015) Districting problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer, Berlin, pp 595–622
Lewenberg Y, Lev O (2016) Divide and conquer: using geographic manipulation to win district-based elections. In: COMSOC-2016, Toulouse. https://www.irit.fr/COMSOC-2016/proceedings/LewenbergLevCOMSOC2016. Accessed 31 July 2016
Mehrotra A, Johnson EL, Nemhauser GL (1998) An optimization based heuristic for political districting. Manag Sci 44:1100–1114
Nagel SS (1972) Computers and the law and politics of redistricting. Polity 5:77–93
Puppe C, Tasnádi A (2009) Optimal redistricting under geographical constraints: why ‘pack and crack’ does not work. Econ Lett 105:93–96
Ricca F, Simeone B (2008) Local search algorithms for political districting. Eur J Oper Res 189:1409–1426
Ricca F, Scozzari A, Simeone B (2008) Weighted Vornoi region algorithms for political districting. Math Comput Model 48:1468–1477
Ricca F, Scozzari A, Simeone B (2011) Political districting: from classical models to recent approaches. 4OR-Q J Oper Res 9:223–254
Tasnádi A (2011) The political districting problem: a survey. Soc Econ 33:543–553
Vickrey W (1961) On the prevention of gerrymandering. Polit Sci Q 76:105–110