Redistricting Algorithms

The goal of the research project is to compare and contrast various mathematical approaches to redistricting. Historically, the requirements of contiguity, compactness, and population balance are used to assess whether or not a proposed districting plan is acceptable. There are many measures for compactness; for most reasonable measures, there are many potential districting plans that would be deemed acceptable; and for problems of realistic size, these criteria are not sufficient to pin down a small number of plans, leading to controversies over whether or not a proposed plan is reasonable. The goal of the project is to study the existing academic literature on these questions, develop additional criteria that capture notions of what it means for a plan to be non-partisan, and develop efficient algorithms to find non-partisan redistricting plan for a few states in the US including New York State.