  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.
