University of Illinois Urbana-Champaign

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

King, Douglas

Content Files
King_Douglas.pdf

Permalink

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

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
Date of Ingest
2012-05-22T00:16:12Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering