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

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

• 批准号: 1408763
• 负责人: Jeff Erickson
• 金额: $ 55万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1408763&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年代中期以来，平面图和近平面图一直是算法研究的沃土，这既是因为它们自然地为实践中出现的许多类型的网络建模，也是因为它们比更一般的图允许更简单和更快的算法。这种图形的算法在地理信息系统、计算机图形学、实体建模、计算机视觉、超大规模集成电路设计、信息可视化、有限元网格生成、计算几何和其他领域都有许多应用。在过去十年中引入的新技术导致了平面图及其推广的新优化算法的爆炸式增长，以及一个小型但不断增长的研究社区的出现，该研究社区利用并贡献了这些技术池；然而，我们遇到了这些技术的局限性。本计划的目标是为平面图和相关图族的几个基本优化问题开发有效的算法。解决现有工具范围之外的问题将引导pi开发下一批技术，这些技术将在该领域保持势头。具体目标包括更快和更简单的精确算法，用于最短路径，最大流量，最小切割和最小成本流的变体，以及用于几种网络设计，聚类和设施定位问题的新的多项式时间近似方案，目前尚无此类方案。pi还将实现和实验评估一些看起来特别有前途的算法，并使结果软件公开可用，以支持学生、研究人员和许多不同计算领域的专业人员的努力。