Published October 29, 2019
| Version Submitted
Journal Article
Open
Fair redistricting is hard
Abstract
Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is -hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is -hard.
Additional Information
© 2019 Elsevier B.V. Received 27 August 2018, Revised 6 February 2019, Accepted 15 April 2019, Available online 28 May 2019. The main ideas in this paper were conceived while the authors were attending an Oberwolfach workshop on "Applied Harmonic Analysis and Data Processing" in March 2018. The authors thank Boris Alexeev and Ruth Greenwood for reading a preliminary version of this paper and providing helpful comments. RK was supported in part by Joel A. Tropp under ONR Award No. N00014-17-12146 and also acknowledges funding provided by the Institute of Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). DGM was partially supported by AFOSR F4FGA06060J007 and AFOSR Young Investigator Research Program award F4FGA06088J001. SV was partially supported by the Simons Algorithms and Geometry (A&G) Think Tank. The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government.Attached Files
Submitted - 1808.08905.pdf
Files
1808.08905.pdf
Files
(582.2 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:cff1e13c0335015180e4ab94ecae0efc
|
582.2 kB | Preview Download |
Additional details
Identifiers
- Eprint ID
- 95824
- Resolver ID
- CaltechAUTHORS:20190528-132709883
Related works
- Describes
- https://arxiv.org/abs/1808.08905 (URL)
Funding
- Office of Naval Research (ONR)
- N00014-17-12146
- Institute for Quantum Information and Matter (IQIM)
- NSF
- PHY-1733907
- Air Force Office of Scientific Research (AFOSR)
- F4FGA06060J007
- Air Force Office of Scientific Research (AFOSR)
- F4FGA06088J001
- Simons Foundation
Dates
- Created
-
2019-05-28Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field