EAGER: Redistricting Design via Clustering in Euclidean and Planar-Graph Metrics

点击翻译按钮获取中文摘要

The award deals with the design and analysis of algorithms for geographical problems, and algorithms for computational problems involving forming clusters of input datapoints. As an example, the project will involve investigation of a particular approach to electoral redistricting by computer, an approach that builds on clustering techniques and concepts. The goals of the project are to design and assess redistricting methods that will yield compact, contiguous districts that are population-balanced to within a difference of one person, to quantitatively evaluate the compactness of the districts, to seek faster algorithms to compute the districts, and to study the degree to which the method is resistant to gerrymandering. One potential impact of this activity is to help inform the ongoing societal discussion of redistricting by demonstrating the availability of a transparent redistricting methods that achieve high-quality fair districting plans. Another potential impact is in the training of new computer scientists. Because research on redistricting addresses a perceived problem in society, it attracts and engages many people, especially those motivated by a desire for positive societal impact. The project will support training both directly and indirectly. First, students, particularly women and members of historically underrepresented groups, will be recruited to assist in performing this research and in disseminating the results. Second, the disseminated results will inspire and encourage people to study computer science. This project will serve as an example of how algorithms can be used for social good. The research draws on the study of the following optimization problem: given an integer k and a set of points in a metric space, find a partitioning of the given points into 'k' clusters so as to minimize the sum of squared intra-cluster distances subject to each cluster being assigned a '1/k' fraction of the locations. Although this problem is computationally intractable, even a locally-optimal solution has desirable characteristics; for example, if the metric space is the Euclidean plane, the clusters can be represented by convex polygons with few sides on average. There are several obstacles to using this approach in practical redistricting, such as: (1) exact locations of people are not available; (2) finding a locally optimal solution can be time-consuming; (3) the Euclidean metric does not take into account geographical barriers. The project will explore ways of overcoming these obstacles. In addition, the project will investigate other questions, such as how well does local search approximate the minimum sum of squared distances, and how easy or difficult is it to find local solutions that give one group a significant political advantage.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.