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

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

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.