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

EAGER：通过欧几里得和平面图度量中的聚类重新划分设计

• 批准号: 1841954
• 负责人: Philip Klein
• 金额: $ 10万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2020-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1841954&HistoricalAwards=false
• 关键词: EAGER; Redistricting; Design; via; Clustering

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.

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

项目成果

Balanced centroidal power diagrams for redistricting

用于重新划分的平衡质心功率图

• DOI: 10.1145/3274895.3274979
• 发表时间: 2018
• 期刊: Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
• 作者: Cohen-Addad, Vincent;Klein, Philip N.;Young, Neal E.
• 通讯作者: Young, Neal E.

New hardness results for planar graph problems in p and an algorithm for sparsest cut

• DOI: 10.1145/3357713.3384310
• 发表时间: 2020-06
• 期刊: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Amir Abboud;Vincent Cohen-Addad;P. Klein

A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs

平面图中有限容量车辆路径的 PTAS

• DOI: 10.1007/978-3-030-24766-9_8
• 发表时间: 2019
• 期刊: WADS 2019
• 作者: Becker, Amariah;Klein, Philip N;Schild, Aaron
• 通讯作者: Schild, Aaron

The impact of highly compact algorithmic redistricting on the rural-versus-urban balance

高度紧凑的算法重新划分对农村与城市平衡的影响

• DOI: 10.1145/3397536.3422249
• 发表时间: 2020
• 期刊: Proceedings of the 28th International Conference on Advances in Geographic Information Systems
• 作者: Wheeler, Archer;Klein, Philip N.
• 通讯作者: Klein, Philip N.

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

• DOI: 10.1109/focs46700.2020.00061
• 发表时间: 2020-09
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Vincent Cohen-Addad;Arnold Filtser;P. Klein;Hung Le