Graph theory models and algorithms for political districting: an approach to inform public policy

King, Douglas

Permalink

https://hdl.handle.net/2142/30931 Copy

Description

Title

Graph theory models and algorithms for political districting: an approach to inform public policy

Author(s)

King, Douglas

Issue Date

2012-05-22T00:16:12Z

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon H.

Doctoral Committee Chair(s)

Shanbhag, Vinayak V.

Committee Member(s)

• Jacobson, Sheldon H.
• Chekuri, Chandra S.
• Sewell, Edward C.

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Operations research
• Political districting
• Plane graph theory
• Local search

Abstract

Political districting is an intractable problem with significant ramifications for political representation. Districts are often required to satisfy some legal constraints, but these are typically not very restrictive, allowing decision-makers to influence the composition of these districts without violating relevant laws. For example, while districts must often comprise a single contiguous area, a vast collection of acceptable solutions (i.e., sets of districts) remains. Choosing the best set of districts from this collection can be treated as a (planar) graph partitioning problem. Such problems are typically intractable, and hence, heuristics such as local search have been adopted to generate good (though suboptimal) solutions in a reasonable time-frame. When districts must be contiguous, effectively applying local search requires an efficient computational method for evaluating contiguity constraints in each iteration; common methods for assessing contiguity can require significant computation as the problem size grows. Practical districting problems, such as those encountered when designing United States Congressional Districts, may need to allocate a very large number of census blocks among a relatively small number of districts, leading to significant computation when assessing contiguity. This dissertation introduces the geo-graph, a new graph model that ameliorates the computational burdens associated with enforcing contiguity constraints in planar graph partitioning when each vertex corresponds to a particular region of the plane called a unit. Through planar graph duality, the geo-graph provides a scale-invariant method for enforcing contiguity constraints in local search. Furthermore, geo-graphs allow district holes (which are typically considered undesirable) to be rigorously and efficiently integrated into the partitioning process. These benefits are realized by exploiting unused facets of the underlying structure of districting problems by both (1) integrating knowledge about the duality between unit boundaries and unit adjacencies, and (2) integrating zone-level knowledge into unit-level decisions through a rigorous link that exists between holes and contiguity. The geo-graph provides fast algorithms that assess zone holes and zone contiguity during local search; the time complexities of these algorithms depend only on the number of zones being created and the number of units whose boundaries share at least one point with the boundary of the unit that local search seeks to transfer in the current iteration. These factors do not necessarily increase with the number of units under consideration, and hence, these algorithms are scale invariant from a theoretical perspective. Moreover, this dissertation finds that these factors scale well in several practical problem instances, suggesting that benefits of the geo-graph can be significant in real-world districting problems.

Graduation Semester

2012-05

Permalink

http://hdl.handle.net/2142/30931

Copyright and License Information

Copyright 2012 Douglas M. King

Owning Collections