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

该奖项涉及地理问题算法的设计和分析，以及涉及形成输入数据点集群的计算问题的算法。例如，该项目将调查一种利用计算机重新划分选区的特殊方法，这是一种建立在分组技术和概念基础上的方法。该项目的目标是设计和评估重新划分选区的方法，这些方法将产生人口平衡到一个人的范围内的紧凑、毗连的地区，定量地评估这些地区的紧凑程度，寻找更快的算法来计算这些地区，并研究该方法抵抗不公正划分选区的程度。这项活动的一个潜在影响是，通过展示实现高质量公平选区计划的透明的选区重新划分方法，帮助为正在进行的关于重新划分选区的社会讨论提供信息。另一个潜在的影响是对新计算机科学家的培训。因为重新划分选区的研究解决了社会中一个被察觉到的问题，它吸引并吸引了许多人，特别是那些渴望产生积极社会影响的人。该项目将直接和间接支持培训。首先，将招募学生，特别是妇女和历史上代表性不足的群体的成员，以协助进行这项研究并传播结果。其次，传播的结果将激励和鼓励人们学习计算机科学。这个项目将成为如何将算法用于社会公益的一个例子。该研究借鉴了对以下优化问题的研究：给定整数k和度量空间中的一组点，找出将给定点划分成‘k’个簇以便最小化平方簇内距离的和，每个簇被分配位置的‘1/k’个分数。虽然这个问题在计算上是困难的，但即使是局部最优解也具有所需的特征；例如，如果度量空间是欧几里得平面，则簇可以由平均具有较少边的凸多边形来表示。在实际的重新划分中使用这种方法有几个障碍，例如：(1)人的确切位置不可用；(2)寻找局部最优解可能很耗时；(3)欧几里德度量没有考虑地理障碍。该项目将探索克服这些障碍的方法。此外，该项目还将调查其他问题，例如本地搜索对最小平方距离和的近似程度如何，以及找到给某个群体带来显著政治优势的本地解决方案的难易程度。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.