{'fraction_non_alphanumeric': 0.0429113323850166, 'fraction_numerical': 0.02112968231389284, 'mean_word_length': 4.1066888619854724, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Alleviating partisan gerrymandering: can math and computers help to eliminate wasted votes?

Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee introduced a new and precise measure of partisan gerrymandering via the so-called"efficiency gap"that computes the absolutes difference of wasted votes between two political parties in a two-party system. Quite importantly from a legal point of view, this measure was found legally convincing enough in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered; the case is now pending in US Supreme Court. In this article, we show the following: (a) We provide interesting mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. To the best of our knowledge, these are the first non-trivial theoretical and algorithmic analyses of this measure of gerrymandering. (b) We provide a simple and fast algorithm that can"un-gerrymander"the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania by bring their efficiency gaps to acceptable levels from the current unacceptable levels. Our work thus shows that, notwithstanding the general worst case approximation hardness of the efficiency gap measure as shown by us,finding district maps with acceptable levels of efficiency gaps is a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure. We believe that, should the US Supreme Court uphold the decision of lower courts, our research work and software will provide a crucial supporting hand to remove partisan gerrymandering.


Introduction and Motivation
Gerrymandering, namely creation of district plans with highly asymmetric electoral outcomes to disenfranchise voters, has continued to be a curse to fairness of electoral systems in USA for a long time in spite of general public disdain for it. Even though the US Supreme Court ruled in 1986 [11] that gerrymandering is justiciable, they could not agree on an effective way of estimating it. Indeed, a huge impediment to removing gerrymandering lies in formulating an effective and precise measure for it that will be acceptable in courts.
In 2006, the US Supreme Court opined [21] that a measure of partisan symmetry may be a helpful tool to understand and remedy gerrymandering. Partisan symmetry is a standard for defining partisan gerrymandering that involves the computation of counterfactuals typically under the assumption of uniform swings. To illustrate lack of partisan symmetry consider a two-party voting district and suppose that Party A wins by getting 60% of total votes and 70% of total seats. In such a case, a partisan symmetry standard would hold if Party B would also win 70% of the seats had it won 60% of the votes in a hypothetical election. Two frequent indicators cited for lack of partisan symmetry are cracking, namely dividing supporters of a specific party between two or more districts when they could be a majority in a single district, and packing, namely filling a district with more and more supporters of a specific party as long as this does not make this specific party the winner in that district.
There have been many theoretical and empirical attempts at remedying the lack of partisan symmetry by "quantifying" gerrymandering and devising redistricting methods to optimize such quantifications using well-known notions such as compactness and symmetry [3, 6-8, 16, 18, 25, 26]. Since it is often simply not possible to go over every possible redistricting map to optimize the gerrymandering measure due to rapid combinatorial explosion, researchers such as [7,22,30] have also investigated designing efficient algorithmic approach for this purpose. In particular, a popular gerrymandering measure in the literature is symmetry, which attempts to quantify the discrepancy between the share of votes and the share of seats of a party [3,16,18,26]. In spite of such efforts, their success in convincing courts to adopt one or more of these measures has been unfortunately somewhat limited to date.
Recently, researchers Stephanopoulos and McGhee in two papers [23,29] have introduced a new gerrymandering measure called the "efficiency gap". Informally speaking, the efficiency gap measure attempts to minimize the absolute difference of total wasted votes between the parties in a two-party electoral system. This measure is very promising in several aspects. Firstly, it provides a mathematically precise measure of gerrymandering with many desirable properties. Equally importantly, at least from a legal point of view, this measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin is gerrymandered; the case is now pending in US Supreme Court [17].

Informal Overview of Our Contribution and Its Significance
Redistricting based on minimizing the efficiency gap measure however requires one to find a solution to an combinatorial optimization problem. To this effect, the contribution of this article is as follows: As a necessary first step towards investigating the efficiency gap measure, in Section 2 we first formalize the optimization problem that corresponds to minimizing the efficiency gap measure.
Subsequently, in Section 3 we study the mathematical properties of the formalized version of the measure. Specifically, Lemma 1 and Corollary 2 show that the efficiency gap measure attains only a finite discrete set of rational values; these properties are of considerable importance in understanding the sensitivity of the measure and in designing efficient algorithms for computing this measure.
Next, in Sections 4 and 5 we investigate computational complexity and algorithm design issues of redistricting based on the efficiency gap measure. Although Theorem 4 shows that in theory one can construct artificial pathological examples for which designing efficient algorithms is provably hard, Theorem 10 and Theorem 11 provide justification as to why the result in Theorem 4 is overly pessimistic for real data that do not necessarily correspond to these pathological examples. For example, assuming that the districts are geometrically compact (y-convex in our terminology), Theorem 11 shows how to find a district map efficiently in polynomial time that minimizes the efficiency gap.
Finally, to show that it is indeed possible in practice to solve the problem of minimization of the efficiency gap, in Section 6 we design a fast randomized algorithm based on the local search paradigm in combinatorial optimization for this problem (cf. Fig. 4). Our resulting software was tested on four electoral data for the 2012 election of the (federal) house of representatives for the US states of Wisconsin [35,36], Texas [37, 38], Virginia [33,34] and Pennsylvania [31,32]. The results computed by our fast algorithm are truly outstanding: the final efficiency gap was lowered to 3.80%, 3.33%, 3.61% and 8.64% from 14.76%, 4.09%, 22.25% and 23.80% for Wisconsin, Texas, Virginia and Pennsylvania, respectively, in a small amount of time. Our empirical results clearly show that it is very much possible to design and implement a very fast algorithm that can "un-gerrymander" (with respect to the efficiency gap measure) the gerrymandered US house districts of four US states.
Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure, namely issues pertaining to seat gain vs. efficiency gap, compactness vs. efficiency gap and the naturalness of original gerrymandered districts.
To the best of our knowledge, our results are first algorithmic analysis and implementation of minimization of the efficiency gap measure. Our results show that it is practically feasible to redraw district maps in a small amount of time to remove gerrymandering based on the efficiency gap measure. Thus, should the Supreme Court uphold the ruling of the lower court, our algorithm and its implementation will be a necessary and valuable asset to remove partisan gerrymandering.

Beyond scientific curiosity: impact on US judicial system
Beyond its scientific implications on the science of gerrymandering, we expect our algorithmic analysis and results to have a beneficial impact on the US judicial system also. Some justices, whether at the Supreme Court level or in lower courts, seem to have a reluctance to taking mathematics, statistics and computing seriously [12,28], For example, during the hearing in our previously cite most recent US Supreme Court case on gerrymandering [17], some justices opined that the math was unwieldy, complicated, and newfangled. One justice called it baloney, and Chief Justice John Roberts dismissed the attempts to quantify partisan gerrymandering by saying "It may be simply my educational background, but I can only describe it as sociological gobbledygook." Our theoretical and computational results show that the math, whether complicated or not (depending on one's background), can in fact yield fast accurate computational methods that can indeed be applied to un-gerrymander the currently gerrymandered maps.

Some Remarks and Explanations Regarding the Technical Content of This Paper
To avoid any possible misgivings or confusions regarding the technical content of the paper as well as to help the reader towards understanding the remaining content of this article, we believe the following comments and explanations may be relevant. We encourage the reader to read this section and explore the references mentioned therein before proceeding further.
We employ a randomized local-search heuristic for combinatorial optimization for our algorithm in Fig. 4. Our algorithmic paradigm is quite different from Markov Chain Monte Carlo simulation, simulated annealing approach, Bayesian methods and related similar other methods (e.g., no temperature parameter, no Gibbs sampling, no calculation of transition probabilities based on Markov chain properties, etc.). Thus, for example, our algorithmic paradigm and analysis for the efficiency gap measure is different and incomparable to that used by researchers for other different measure, such as by Herschlag, Ravier and Mattingly [19], by Fifield et al. [13] or by Cho and Liu [8].
For a detailed exposition of randomized algorithms the reader is referred to excellent textbooks such as [2,24] and for a detailed exposition of local-search algorithmic paradigm in combinatorial optimization the reader is referred to the excellent textbook [1].
While we do provide several non-trivial theoretical algorithmic results, we do not provide any theoretical analysis of the randomized algorithm in Fig. 4. The justification for this is that, due to Theorem 4 and Lemma 12, no such non-trivial theoretical algorithmic complexity results exist in general assuming P = NP for deterministic local-search algorithms or assuming RP = NP for randomized local-search algorithms. One can attribute this to the usual "difference between theory and practice" doctrine.
For readers unfamiliar with the complexity-theoretic assumptions P = NP and RP = NP, these are core complexity-theoretic assumptions that have been routinely used for decades in the field of algorithmic complexity analysis. For example, starting with the famous Cook's theorem [9] in 1971 and Karp's subsequent paper in 1972 [20], the P = NP assumption is the central assumption in structural complexity theory and algorithmic complexity analysis. For a detailed technical coverage of the basic structural complexity field, we refer the reader to the excellent textbook [4].
In this article we use the data at the county level as opposed to using data at finer (more granular) level such as the "Voting Tabulation District" (VTD) level (VTDs are the smallest units in a state for which the election data are available). The reason for this is as follows. Note that our algorithmic approach already returns an efficiency gap of below 4% for three states (namely, WI, TX and VA), and for PA it cuts down the current efficiency gap by a factor of about 3 (cf. Table 2). This, together with the observation in [29, pp. 886-888] that the efficiency gap should not be minimized to a very low value to avoid unintended consequences, shows that even just by using county-level data our algorithm can already output almost desirable (if not truly desirable) values of the efficient gap measure and thus, by Occam's razor principle 1 widely used in computer science, we should not be using more data at finer levels. In fact, using more data at a finer level may lead to what is popularly known as "overfitting" in the context of machine learning and elsewhere [5] that may hide its true performance on yet unexplored maps. In this context, our suggestion to future algorithmic researchers in this direction is to use a minimal amount of data that is truly necessary to generate an acceptable solution.
In this article we are not comparing our approaches empirically to those in existing literature such as in [8,13,19]. The reason for this is that, to the best of our knowledge, there is currently no other published work that gives a software to optimize the efficiency gap measure. In fact, it would be grossly unfair to other existing approaches if we compare our results with their results. For example, suppose we consider an optimal result using an approach from [8] and find that it gives an efficiency gap of 15% whereas the approach in this article gives an efficiency gap of 5%. However, it would be grossly unfair to say that, based on this comparison, our algorithm is better than the one in [8] since the authors in [8] never intended to minimize the efficiency gap. Furthermore, even the two maps cannot be compared directly by geometric methods since no court has so far established a firm and unequivocal ground truth on gerrymandering by having a ruling of the following form: [court]: "a district map is gerrymandered if and only if such-and-such conditions are satisfied" 1 Occam's razor principle [27] states that "Entia non sunt multiplicanda praeter necessitatem" (i.e., more things should not be used than are necessary). It is also known as rule of parsimony in biological context [14]. Overfitting is an example of violation of this principle.
(the line is crossed out above just to doubly clarify that such a ruling does not exist).
For certain scientific research problems, algorithmic comparisons are possible because of the existence of ground truths (also called "gold standards" or "benchmarks"). For example, different algorithmic approaches for reverse engineering causal relationships between components of a biological cellular system can be compared by evaluating how close the methods under investigation are in recovering known gold standard networks using widely agreed upon metrics such as recall rates or precision values [10]. Unfortunately, for gerrymandering this is not the case and, in our opinion, comparison of algorithms for gerrymandering that optimize substantially different objectives should be viewed with a grain of salt.
The main research goal of this paper is to minimize the efficiency gap measure exactly as introduced by Stephanopoulos and McGhee in [23,29]. However, should future researchers like to introduce additional computable constraints or objectives, such as compactness or respect of community boundaries, on top of our efficiency gap minimization algorithm, it is a conceptually easy task to modify our algorithm in Fig. 4 for this purpose. For example, to introduce compactness on top of minimization of the efficiency gap measure, the following two lines in Fig. 4 if Effgap κ (P, Q 1 , . . . , Q κ ) < Effgap κ (P, Q 1 , . . . , Q κ ) then should be changed to something like (changes are indicated in bold): Based on [23,29], we abstract our problem in the following manner. We are given a rectilinear polygon P without holes. Placing P on a unit grid of size m × n, we will identify an individual unit square (a "cell") on the i th row and j th column in P by p i,j for 0 ≤ i < m and 0 ≤ j < n (see Fig. 1). For each cell p i,j ∈ P, we are given the following three integers: an integer Pop i,j ≥ 0 (the "total population" inside p i,j ), and two integers PartyA i,j , PartyB i,j ≥ 0 (the total number of voters for Party A and Party B, respectively) such that PartyA i,j + PartyB i,j = Pop i,j .
Let |P| = | {p i,j : p i,j ∈ P} | denote the "size" (number of cells) of P. For a rectilinear polygon Q included in the interior of P (i.e., a connected subset of the interior of P), we defined the following quantities: Our problem can now be defined as follows.
Input: a rectilinear polygon P with Pop i,j , PartyA i,j , PartyB i,j for every cell p i,j ∈ P, and a positive integer 1 < κ ≤ |P|.
Assumption: P has at least one κ-equipartition.

Mathematical Properties of Efficiency Gaps: Set of Values Attainable by the Efficiency Gap Measure
The following lemma sheds some light on the set of rational numbers that the total efficiency gap of a κequipartition can take. As an illustrative example, if we just partition the polygon P into κ = 2 regions, then Effgap 2 (P, Q 1 , Q 2 ) can only be one of the following 3 possible values: for some z ∈ {0, 1, . . . , κ} and some Proof. To prove (a), consider any κ-equipartition Letting z be the number of r j 's that are equal to 3/2, it follows that Corollary 2 Using the reverse triangle inequality of norms, the absolute difference between two successive values of Effgap κ (P, Q 1 , . . . , Q κ ) is given by Corollary 3 (see also [29, p. 853]) For any κ-equipartition Q 1 , . . . , Q κ of P, consider the following quantities as defined in [29]: (Normalized) seat margin of Party A: Recall that, for any ρ ≥ 1, an approximation algorithm with an approximation ratio of ρ (or, simply an ρapproximation) is a polynomial-time solution of value at most ρ times the value of an optimal solution [15].
Theorem 4 Assuming P = NP, for any rational constant ε ∈ (0, 1), the MIN-WVP κ problem for a rectilinear polygon P does not admit a ρ-approximation algorithm for any ρ and all 2 ≤ κ ≤ ε|P|. Proof of Theorem 4. We reduce from the NP-complete PARTITION problem [15] which is defined as follows: given a set of n positive integers A = {a 0 , . . . , a n−1 }, decide if there exists a subset A ⊂ A such that a i ∈A a i = a j / ∈A a j . Note that we can assume without loss of generality that n is sufficiently large and each of a 0 , . . . , a n−1 is a multiple of any fixed positive integer. For notational convenience, let ∆ = n−1 j=0 a j . Let µ ≥ 0 be such that κ = 2 + µn (we will later show that µ is at most the constant 6ε 1−ε ). Our rectilinear polygon P, as illustrated in Fig. 2 (A), consists of a rectangle C = {p i,j | 0 ≤ i ≤ n, 0 ≤ j ≤ 2} of size 3 × (n + 1) with additional µn cells attached to it in any arbitrary manner to make the whole figure a connected polygon without holes. For convenience, let D = {p i,j | p i,j / ∈ C} be the set of the additional µn cells. The relevant numbers for each cell are as follows: First, we show how to select a rational constant µ such that any integer κ in the range [ 2, ε|P| ] can be realized. Assume that κ = ε |P| ∈ [ 2, ε|P| ] for some ε . Since |P| = 3(n + 1) + µn the following calculations hold:  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270   360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270 270  360 360 360  270 270    have a population of Pop(P) κ = ∆ and thus each p i,j ∈ D of population ∆ must be a separate partition by itself. K Using Claim 4.1 we can simply ignore all p i,j ∈ D in the calculation of of efficiency gap of a valid solution of P and it follows that the total efficiency gap of a κ-equipartition of P is identical to that of a 2-equipartition of C. A proof of the theorem then follows provided we prove the following two claims.
(soundness) If the PARTITION problem does not have a solution then OPT 2 (C) = ∆.
(completeness) If the PARTITION problem has a solution then OPT 2 (C) = 0.
Proof of soundness (refer to Fig. 2

(B))
Suppose that there exists a valid solution (i.e., a 2-equipartition) C 1 , C 2 of MIN-WVP 2 for C with p 0,0 ∈ C 1 , p 0,2 ∈ C 2 , and let A = {a j | p 1,j ∈ C 1 }. Then, and thus A is a valid solution of PARTITION, a contradiction! Thus, assume that both p 0,0 and p 0,2 belong to the same partition, say C 1 . Then, since Pop 0,0 +Pop 0,4 = ∆ = Pop(C) 2 , every p 1,j must belong to C 2 . Moreover, every p i,j ∈ C with η i,j = 0 must belong to C 1 since otherwise C 1 will not be a connected region. This provides Pop(C 1 ) = Pop(C 2 ) = ∆, showing that C 1 , C 2 is indeed a valid solution (i.e., a 2-equipartition) of MIN-WVP 2 for C. The total efficiency gap of this solution can be calculated as Proof of completeness (refer to Fig. 2

(C))
Suppose that there is a valid solution of A ⊂ A of PARTITION and consider the two polygons By straightforward calculation, it is easy to verify the following: • Pop(C 1 ) = a j ∈A a j + n j=0 Pop 2,j = ∆, Pop(C 2 ) = a j / ∈A a j + n j=0 Pop 2,j = ∆, and thus C 1 , C 2 is a valid solution (i.e., a 2-equipartition) of MIN-WVP 2 for C.

Efficient Algorithms Under Realistic Assumptions
Although Theorem 4 seems to render the problem MIN-WVP κ intractable in theory, our empirical results show that the problem is computationally tractable in practice. This is because in real-life applications, many constraints in the theoretical formulation of MIN-WVP κ are often relaxed. For example: (i) Restricting district shapes: Individual partitions of the κ-equipartition of P may be restricted in shape. For example, 37 states require their legislative districts to be reasonably compact and 18 states require congressional districts to be compact [39].
(ii) Variations in district populations: A partition Q 1 , . . . , Q κ of P is only approximately κ-equipartition, i.e., Pop(Q 1 ), . . . , Pop(Q κ ) are approximately, but not exactly, equal to Pop(P) /κ. For example, the usual federal standards require equal population as nearly as is practicable for congressional districts but allow more relaxed substantially equal population (e.g., no more than 10% deviation between the largest and smallest district) for state and local legislative districts [39].
In this section, we explore algorithmic implications of these types of relaxations of constraints for MIN-WVP κ .

The Case of Two Stable and Approximately Equal Partitions
This case considers constraints (ii) and (iii). The following definition of "near partitions" formalizes the concept of variations in district populations.
The next definition of "stability" formalizes the concept of bounding away from zero the efficiency gap of each partition.
Definition 6 (Stability) Let κ ∈ N, let P be an instance of MIN-WVP κ , and let φ def = Q 1 , . . . , Q κ be a partition for P. We say that φ is γ-stable, for some γ > 0, if for all i ∈ {1, . . . , κ}, we have Definition 7 (Canonical solution) Let P be an instance of MIN-WVP 2 . Let t ∈ N. Let B be the partition of P obtained as follows: We partition P into m/t · n/t rectangles, where each rectangle consists of the intersection of t rows with t columns, except possibly for the rectangles that are incident to the right-most and the bottom-most boundaries of P. We refer to the rectangles in B as t-basic (see figure 3). Let T be the set of cells consisting of the union of the left-most column of P, the top row of P, and for each t-basic rectangle X, the bottom row of X, and the right-most column of X, except for the cell that is next to the top cell of that column (see figure 3). We refer to T as the t-basic tree For each t-basic rectangle X, we define its interior to be the set of cells in X that are at distance at least 2 from T . A solution φ def = Z 1 , Z 2 of P is called t-canonical if it satisfies the following properties.
(2) Let X be a t-basic rectangle, and let X be its interior. For each i ∈ {1, 2}, let A i be the set of connected components of X ∩ Z i . Then, for each Y ∈ A 1 , there exists a unique cell in T 1 that is adjacent to both Y and T . Moreover, all other cells in X \ (X ∪ T ) are in Z 2 (see Figure 3).

Lemma 8
Let P be an instance of MIN-WVP 2 . Suppose that there are no empty cells and the maximum number of people in any cell of P is C. Let γ > 0, and suppose that there exists a γ-stable solution φ def = Q 1 , Q 2 for P . Then, for any ε > 0, at least one of the following conditions hold: (1) Either Q 1 or Q 2 is contained in some 1/ε-basic rectangle.
(2) There exists a 1/ε -canonical δ-near solution φ = Q 1 , Q 2 of P, for some δ = O(εC), such that for all Proof. It suffices to show that if condition (1) does not hold, then condition (2) does. We define a partition φ def = Q 1 , Q 2 of P as follows. We initialize Q 1 to be empty. Let T be the 1/ε-basic tree. We add T 1 to Q 1 . For each 1/ε-basic rectangle X, let X be its interior. For each i ∈ {1, 2}, let A i be the set of connected components of X ∩ Q 1 . Since φ is a valid solution, we have that Q 1 is connected. Since condition (1) does not hold, it follows that Q 1 intersects at least two 1/ε-basic rectangles. Therefore, each component W ∈ A 1 must contain some cell c W on the boundary of X . By construction, c W must be incident to some cell c W that is incident to T . We add c W to Q 1 . Repeating this process for all basic rectangles, and for all components W as above. Finally, we define Q 2 = P \ Q 1 . This completes the definition of the partition φ def = Q 1 , Q 2 of P. It remains to show that this is the desired solution. First, we need to show that φ is a valid solution. To that end, it suffices to show that both Q 1 and Q 2 are connected. The fact that Q 1 is connected follows directly from its construction. To show that Q 2 is connected we proceed by induction on the construction of Q 1 . Initially, Q 1 consists of just the cells in T , and thus its complement is clearly connected. When we consider a component W , we add W ∪ {c W } to Q 1 .
Since we add only a single cell that is incident to both W and Q 1 , it follows inductively that Q 1 remains simply connected (that is, it does not contain any holes), and therefore its complement remains connected. This concludes the proof that both Q 1 and Q 2 are connected, and therefore φ is a valid solution.
The solutions φ and φ can disagree only on cells that are not in the interior of any basic rectangle. All these cells are contained in the union of O(εm) rows and (εn) columns. Thus, the total number of voters in these cells is at most O(Cεnm). It follows that for each i ∈ {1, 2}, we have |PartyA Since there are no empty cells, we have Pop(P) ≥ nm. It follows that for all i ∈ {1, 2}, we have Thus φ is δ-near, for some δ = O(εC), which concludes the proof. K Lemma 9 Let γ > 0. Let P be an instance of MIN-WVP 2 . Suppose that there are no empty cells and the maximum number of people in any cell of P is C. Suppose that there exists a δ-stable partition φ def = Q 1 , Q 2 of P . Then, for any fixed ε > 0, there exists an algorithm which given P computes some δ-near Proof. We can check whether there exist a partition φ def = Q 1 , Q 2 satisfying the conditions, and such that either Q 1 or Q 1 is contained in the interior of a single 1/ε-basic rectangle. This can be done by trying all 1/ε-basic rectangles, and all possible subsets of the interior of each 1/ε-basic rectangle, in time It remains to consider the case where neither of Q 1 and Q 2 is contained in the interior of any 1/ε-basic rectangle. It follows that condition (2)  Proof. It follows from Lemma 9 by setting ε = min{ε, O(δ/C)}. K

The Case of Convex Shaped Partitions
This case encompasses constraint (i) since convexity has been used in gerrymandering studies such as [40] as a measure of compactness to examine how redistricting reshapes the geography of congressional districts. We recall that some X ⊆ R 2 is called y-convex if for every vertical line , we have that X ∩ is either empty, or a line segment. We also say that a κ-partition Q 1 , . . . , Q κ of P is y-convex if for all i ∈ {1, . . . , κ}, Q i is y-convex.
Theorem 11 Let P be a rectilinear polygon realized in the m × n grid, and let N = Pop(P) be the total population on P. There exists an algorithm for computing a y-convex κ-equipartition of P of minimum efficiency gap, with running time N O(κ) . In particular, the running time is polynomial when the total population is polynomial and the total number of partitions is a constant.
Proof. Let P * = Q * 1 , . . . , Q * κ be a y-convex κ-equipartition of P of minimum efficiency gap. For any i ∈ {1, . . . , n}, let C i be the i-th column of P. We observe that for all i ∈ {1, . . . , n}, and for all j ∈ {1, . . . , κ}, we have that Q * j ∩ C i is either empty, or consists of a single rectangle of width 1. Let C i be the set of all partitions of C i into exactly κ (possibly empty) segments, each labeled with a unique integer in {1, . . . , κ}. We further define . The algorithm proceeds via dynamic programming. For each i ∈ {1, . . . , n}, let . . , κ}, the unique set Y ∈ Z 1 labeled j satisfies a 1,j = PartyA(Y ) and b 1,j = PartyB(Y ).
For each i ∈ {1, . . . , n} we inductively compute the set F i of all feasible X i ∈ I i . This can clearly be done in time N O(κ) . It is immediate that for all i ∈ {1, . . . , n}, there exists some X i ∈ I i that achieves efficiency gap equal to the restriction of P * on the union of the first i columns. Thus, by induction on i, the algorithm computes a feasible solution with optimal efficiency gap. K

Experimental Results for Real Data on Four Gerrymandered States
To show that it is indeed possible in practice to solve the problem of minimization of the efficiency gap, we design a fast randomized algorithm based on the local search paradigm for this problem. Our algorithm starts with a given Q 1 , . . . , Q κ partition of the input state P. Note that Q 1 , . . . , Q κ was only an approximate equipartition in the sense that the values Pop(Q 1 ), . . . , Pop(Q κ ) are as close to each other as practically possible but need not be exactly equal (cf. US Supreme Court ruling in Karcher v. Daggett 1983). For designing alternate valid district plans, we therefore allow any partition Q 1 , . . . , Q κ of P such that, for every j, start with the current districts, say Q 1 , . . . , Q κ repeat µ times ( * µ was set to 100 in actual run * ) select a random r from the set {0, 1, . . . , k} for some 0 < k < |V | ( * k = 20 in actual run * ) select r nodes v 1 , . . . , v r from G at random ( * Note that a node is a county or part of a county * )  Proof. This follows from the proof of Theorem 4 once observes that the specific instance of the MIN-WVP κ problem created in the reduction of the theorem has exactly one (trivial) non-optimal solution and every other valid solution is an optimal solution. K

Results and Implications
Our resulting software was tested on four electoral data for the 2012 election of the ( Fig. 4 on the four real data-sets are tabulated in Table 2, and the corresponding maps are shown in Fig. 5 A closer look at the new district maps shown in Fig. 5-8 also reveal the following interesting insights: Seat gain vs. efficiency gap. Lowering the efficiency gap from 15% to 3.75% for the state of Wisconsin did not affect the total seat allocation (3 democrats vs. 5 republicans) between the two parties. Indeed, this further reinforces the assertion in [29] that the efficiency gap and partisan symmetry are different concepts, and thus fewer absolute difference of wasted votes does not necessarily lead to seat gains for the loosing party.
Compactness vs. efficiency gap. The new district maps for the state of Virginia reveals an interesting aspect. Our new district map have fewer districts that are oddly shaped compared to the map used for the 2012 election 4 , even though minimizing wasted votes does not take into consideration shapes of districts.
How natural are gerrymandered districts? Since our algorithm applies a sequence of carefully chosen semi-random perturbations to the original gerrymandered districts to drastically lower the absolute difference of wasted votes, one can hypothesize that the original gerrymandered districts are far from being a product of arbitrarily random decisions. However, to reach a definitive conclusion regarding this point, one would need to construct a suitable null model, which we do not have yet.

Conclusion and future research
In this article we have performed algorithmic analysis of the recently introduced efficiency gap measure for gerrymandering both from a theoretical (computational complexity) as well as a practical (software development and testing on real data) point of view. The main objective of the paper was to provide a scientific analysis of the efficiency gap measure and to provide a crucial supporting hand to remove partisan gerrymandering should the US courts decide to recognize efficiency gap as at least a partially valid measure of gerrymandering. Of course, final words on resolving gerrymandering is up to the US judicial systems.