{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T02:35:13Z","timestamp":1782441313524,"version":"3.54.5"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T00:00:00Z","timestamp":1591315200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T00:00:00Z","timestamp":1591315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1160995"],"award-info":[{"award-number":["IIS-1160995"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1160995"],"award-info":[{"award-number":["IIS-1160995"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1814931"],"award-info":[{"award-number":["IIS-1814931"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1423230"],"award-info":[{"award-number":["CCF-1423230"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1453472"],"award-info":[{"award-number":["1453472"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s10878-020-00589-x","type":"journal-article","created":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T05:02:21Z","timestamp":1591333341000},"page":"512-546","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering"],"prefix":"10.1007","volume":"40","author":[{"given":"Tanima","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5614-5477","authenticated-orcid":false,"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Palmieri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zainab","family":"Al-Qurashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,6,5]]},"reference":[{"key":"589_CR1","volume-title":"Local search in combinatorial optimization","year":"2003","unstructured":"Aarts E, Lenstra JK (eds) (2003) Local search in combinatorial optimization. Princeton University Press, Princeton"},{"key":"589_CR2","volume-title":"The probabilistic method","author":"N Alon","year":"2016","unstructured":"Alon N, Spencer JH (2016) The probabilistic method. Wiley Inc., Hoboken"},{"key":"589_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0962-6298(01)00068-3","volume":"21","author":"M Altman","year":"2002","unstructured":"Altman M (2002) A Bayesian approach to detecting electoral manipulation. Polit Geogr 21:39\u201348","journal-title":"Polit Geogr"},{"issue":"1","key":"589_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J Assoc Comput Mach 41(1):153\u2013180","journal-title":"J Assoc Comput Mach"},{"key":"589_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural complexity I","author":"JL Balcazar","year":"1995","unstructured":"Balcazar JL, Diaz J, Gabarr\u00f3 J (1995) Structural complexity I. Springer, Berlin"},{"key":"589_CR6","volume-title":"Model selection and multimodel inference","author":"KP Burnham","year":"2002","unstructured":"Burnham KP, Anderson DR (2002) Model selection and multimodel inference. Springer, Berlin"},{"key":"589_CR7","first-page":"213","volume":"33","author":"EB Cain","year":"1985","unstructured":"Cain EB (1985) Simple vs. complex criteria for partisan gerrymandering: a comment on Niemi and Grofman. UCLA Law Rev 33:213\u2013226","journal-title":"UCLA Law Rev"},{"issue":"4","key":"589_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1089\/elj.2015.0317","volume":"14","author":"J Chen","year":"2015","unstructured":"Chen J, Rodden J (2015) Cutting through the thicket: redistricting simulations and the detection of partisan gerrymanders. Elect Law J 14(4):331\u2013345","journal-title":"Elect Law J"},{"key":"589_CR9","unstructured":"Cho WKT (2017) Measuring partisan fairness: how well does the efficiency gap guard against sophisticated as well as simple-minded modes of partisan discrimination?. Univ Pa Law Rev 166(1), Article 2"},{"issue":"4","key":"589_CR10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1089\/elj.2016.0384","volume":"15","author":"WKT Cho","year":"2016","unstructured":"Cho WKT, Liu YY (2016) Toward a talismanic redistricting tool: a computational method for identifying extreme redistricting plans. Elect Law J Rules Polit Policy 15(4):351\u2013366","journal-title":"Elect Law J Rules Polit Policy"},{"key":"589_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0962-6298(99)00047-5","volume":"19","author":"C Cirincione","year":"2000","unstructured":"Cirincione C, Darling TA, O\u2019Rourke TG (2000) Assessing South Carolina\u2019s 1990s congressional redistricting. Polit Geogr 19:189\u2013211","journal-title":"Polit Geogr"},{"key":"589_CR12","doi-asserted-by":"crossref","unstructured":"Cook SA (1971) The complexity of theorem proving procedures. In 3rd annual ACM symposium on the theory of computing, pp 151-158","DOI":"10.1145\/800157.805047"},{"key":"589_CR13","doi-asserted-by":"publisher","DOI":"10.1002\/9781119162254","volume-title":"Models and algorithms for biomolecules and molecular networks","author":"B DasGupta","year":"2016","unstructured":"DasGupta B, Liang J (2016) Models and algorithms for biomolecules and molecular networks. Wiley, Hoboken"},{"key":"589_CR14","doi-asserted-by":"crossref","unstructured":"Davis v. Bandemer (1986) 478 US 109","DOI":"10.1016\/B978-0-444-01082-7.50034-5"},{"issue":"2","key":"589_CR15","first-page":"38","volume":"16","author":"S Doyle","year":"2015","unstructured":"Doyle S (2015) A graph partitioning model of congressional redistricting. Rose-Hulman Undergr Math J 16(2):38\u201352","journal-title":"Rose-Hulman Undergr Math J"},{"key":"589_CR16","first-page":"1005","volume":"38","author":"DL Faigman","year":"1989","unstructured":"Faigman DL (1989) To have and have not: assessing the value of social science to the law as science and policy. Emory Law J 38:1005\u20131095","journal-title":"Emory Law J"},{"key":"589_CR17","volume-title":"A new automated redistricting simulator using Markov chain Monte Carlo","author":"B Fifield","year":"2018","unstructured":"Fifield B, Higgins M, Imai K, Tarr A (2018) A new automated redistricting simulator using Markov chain Monte Carlo. Princeton University, Princeton"},{"issue":"4","key":"589_CR18","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch WM (1971) Toward defining the course of evolution: minimum change for a specified tree topology. Syst Zool 20(4):406\u2013416","journal-title":"Syst Zool"},{"key":"589_CR19","volume-title":"Computers and intractability\u2013a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability\u2013a guide to the theory of NP-completeness. W. H. Freeman & Co., San Francisco"},{"key":"589_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theor Comput Sci 1:237\u2013267","journal-title":"Theor Comput Sci"},{"issue":"2","key":"589_CR21","doi-asserted-by":"publisher","first-page":"514","DOI":"10.2307\/2111417","volume":"38","author":"A Gelman","year":"1994","unstructured":"Gelman A, King G (1994) A unified method of evaluating electoral systems and redistricting plans. Am J Polit Sci 38(2):514\u2013554","journal-title":"Am J Polit Sci"},{"key":"589_CR22","unstructured":"Gill v. Whitford (2017) US Supreme Court docket no 16-1161, decision pending"},{"key":"589_CR23","unstructured":"Herschlag G, Ravier R, Mattingly JC (2017) Evaluating partisan gerrymandering in Wisconsin. arXiv:1709.01596"},{"issue":"3","key":"589_CR24","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1017\/S0007123400006888","volume":"24","author":"S Jackman","year":"1994","unstructured":"Jackman S (1994) Measuring electoral bias: Australia, 1949\u201393. Brit J Polit Sci 24(3):319\u2013357","journal-title":"Brit J Polit Sci"},{"key":"589_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85\u2013103"},{"key":"589_CR26","unstructured":"League of United Latin American Citizens v. Perry, 548 US 399 (2006)"},{"key":"589_CR27","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.swevo.2016.04.004","volume":"30","author":"YY Liu","year":"2016","unstructured":"Liu YY, Wendy K, Cho T, Wang S (2016) PEAR: a massively parallel evolutionary computational approach for political redistricting optimization and analysis. Swarm Evolut Comput 30:78\u201392","journal-title":"Swarm Evolut Comput"},{"issue":"1","key":"589_CR28","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1111\/lsq.12033","volume":"39","author":"E McGhee","year":"2014","unstructured":"McGhee E (2014) Measuring partisan bias in single-member district electoral systems. Legis Stud Q 39(1):55\u201385","journal-title":"Legis Stud Q"},{"key":"589_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge"},{"issue":"4","key":"589_CR30","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.2307\/2131686","volume":"52","author":"RG Niemi","year":"1990","unstructured":"Niemi RG, Grofman B, Carlucci C, Hofeller T (1990) Measuring compactness and the role of a compactness standard in a test for partisan and racial gerrymandering. J Polit 52(4):1155\u20131181","journal-title":"J Polit"},{"issue":"4","key":"589_CR31","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.2307\/1954541","volume":"72","author":"RG Niemi","year":"1978","unstructured":"Niemi RG, Deegan J (1978) A theory of political districting. Am Polit Sci Rev 72(4):1304\u20131323","journal-title":"Am Polit Sci Rev"},{"key":"589_CR32","unstructured":"\u201cOckham\u2019s Razor\u201d, Encyclop\u00e6dia Britannica (2010)"},{"key":"589_CR33","volume-title":"Redistricting, a devil\u2019s dictionary","author":"O Pierce","year":"2011","unstructured":"Pierce O, Larson J, Beckett L (2011) Redistricting, a devil\u2019s dictionary. ProPublica, Manhattan"},{"key":"589_CR34","unstructured":"\u201cRedrawing the map on redistricting 2010: a national study\u201d (Azavea White Paper, Azavea, 2009; https:\/\/cdn.azavea.com\/com.redistrictingthenation\/pdfs\/Redistricting_The_Nation_White_Paper_2010.pdf)"},{"key":"589_CR35","unstructured":"Rucho et\u00a0al. v. Common Cause et\u00a0al., No. 18-422, argued March 26, 2019\u2014decided June 27"},{"issue":"4","key":"589_CR36","first-page":"1659","volume":"81","author":"JE Ryan","year":"2003","unstructured":"Ryan JE (2003) The limited influence of social science evidence in modern desegregation cases. N C Law Rev 81(4):1659\u20131702","journal-title":"N C Law Rev"},{"issue":"2","key":"589_CR37","first-page":"831","volume":"82","author":"N Stephanopoulos","year":"2015","unstructured":"Stephanopoulos N, McGhee E (2015) Partisan gerrymandering and the efficiency gap. Univ Chicago Law Rev 82(2):831\u2013900","journal-title":"Univ Chicago Law Rev"},{"key":"589_CR38","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/bs.3830120309","volume":"12","author":"J Thoreson","year":"1967","unstructured":"Thoreson J, Liittschwager J (1967) Computers in behavioral science: legislative districting by computer simulation. Behavioral Science 12:237\u2013247","journal-title":"Behavioral Science"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00589-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00589-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00589-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T19:11:46Z","timestamp":1666811506000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00589-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["589"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00589-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,5]]},"assertion":[{"value":"5 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}