AF: Medium: Collaborative Research: Fast and accurate optimization in planar graphs and beyond

AF：中：协作研究：平面图及其他领域的快速准确优化

• 批准号: 1409520
• 负责人: Philip Klein
• 金额: $ 65万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1409520&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Fast

A planar graph is a network drawn on the plane so that no edges cross. Planar and near-planar graphs have been fertile ground for algorithms research since the mid-1950s, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs.  Algorithms for such graphs find numerous applications in geographic information systems, computer graphics, solid modeling, computer vision, VLSI design, information visualization, finite-element mesh generation, computational geometry, and other areas.  New techniques introduced in the last ten years have led to an explosion of new optimization algorithms for planar graphs and their generalizations, as well as the emergence of a small but growing research community that draws on and contributes to this pool of techniques; however, we are coming up against limitations of these techniques.The goal of this project is to develop efficient algorithms for several fundamental optimization problems in planar graphs and related graph families.  Working on problems just outside the range of existing tools will lead the PIs toward developing the next batch of techniques that will maintain momentum in the field.  Specific targets include faster and simpler exact algorithms for variants of shortest paths, maximum flows, minimum cuts, and minimum-cost flows, as well as new polynomial-time approximation schemes for several network design, clustering, and facility location problems for which no such schemes are currently known.  The PIs will also implement and experimentally evaluate some algorithms that appear particularly promising, and make the resulting software publicly available, to support the efforts of students, researchers, and professionals in many different areas of computing.

平面图是在平面上绘制的网络，因此没有边交叉。自20世纪50年代中期以来，平面图和近平面图一直是算法研究的沃土，这既是因为它们自然地模拟了实践中出现的许多类别的网络，也是因为它们允许比更一般的图更简单和更快的算法。此类图的算法在地理信息系统，计算机图形学，实体建模，计算机视觉，VLSI设计，信息可视化，有限元网格生成、计算几何和其他领域。在过去十年中引入的新技术导致了平面图及其推广的新优化算法的爆炸式增长，以及一个小型但不断增长的研究社区的出现，该研究社区借鉴并有助于这一技术池;但是，在此情况下，本项目的目标是为平面图和相关图族中的几个基本优化问题开发有效的算法，研究现有工具范围之外的问题将引导PI朝着开发下一批技术的方向发展，这些技术将保持该领域的发展势头。具体目标包括更快、更简单的最短路径、最大流、最小割和最小成本流的精确算法，以及用于几种网络设计、聚类、和设施选址问题，目前还没有这样的计划。PI还将实施和实验评估一些算法，似乎特别有前途，并使最终的软件公开，以支持学生的努力，研究人员和专业人士在许多不同领域的计算。

项目成果

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.