HackerPapers

arXiv:1808.08905cs.CC

Fair redistricting is hard

Richard Kueng, Dustin G. Mixon, Soledad Villar

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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 NP-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 NP-hard.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.DSData Structures and Algorithms

On Hacker News

No comments linking this paper were found in the collected sources. Found in 2 HN submissions from Aug 2018 to Aug 2018. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.