CAREER: Geometric Techniques for Topological Graph Algorithms

职业：拓扑图算法的几何技术

• 批准号: 2237288
• 负责人: Hung Le
• 金额: $ 65.55万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2028-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2237288&HistoricalAwards=false
• 关键词: CAREER; Geometric; Techniques; Topological; Graph

Classical techniques for designing graph algorithms do not assume structures of input graphs and therefore suffer from worst-case guarantees by artificial instances. Graphs arising in practical applications, including logistics and planning, very large-scale integration (VLSI) design, image processing, and robot navigation, often have nice topological structures: they can be drawn on the plane without (or with a few) edge crossings. Can these structures be exploited for algorithmic advantage? Research on this question has produced powerful algorithmic techniques. Nevertheless, algorithm designers have exploited these techniques to their limits over the past two decades. This project aims to develop a new class of techniques inspired by geometry counterparts that could overcome the limitations of the existing ones. The central idea is to study the metric space induced by shortest path distances of topological graphs and translate algorithmic ideas from discrete geometry to solve problems. In addition to potential impacts on practical applications, this project outlines specific plans to train students at both graduate and undergraduate levels; the practical aspects of this project would particularly be appealing to students from different backgrounds. The project also plans to disseminate state-of-the-art algorithm design techniques for topological graphs. This project will focus on two specific research thrusts. The first studies graph embeddings for designing approximation algorithms. This direction is inspired by the success of embedding techniques for general metrics. The goal is to develop new relaxations of the traditional metric embedding by taking topology into account, specifically focusing on designing approximation algorithms. The second thrust concerns different geometric structures of topological graphs. Developing new geometric structures has resulted in recent breakthroughs in topological graph algorithms. The project proposes an in-depth investigation of geometric structures, including various types of decompositions and dimensions inspired by those studied in geometry. Both thrusts complement each other well: understanding these structures gives insights into what it takes to construct the embeddings and vice versa. This project also includes a number of algorithmic problems that can be settled by geometric techniques for which the traditional techniques fail.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.

设计图形算法的经典技术不假定输入图的结构，因此受到人工实例保证的最坏情况。在实用应用中产生的图形，包括物流和计划，非常大规模集成（VLSI）设计，图像处理和机器人导航，通常具有不错的拓扑结构：可以在飞机上绘制它们，而无需（或具有几个）边缘交叉口。这些结构是否可以利用算法优势？对这个问题的研究产生了强大的算法技术。尽管如此，在过去的二十年中，算法设计师将这些技术利用了它们的极限。该项目旨在开发一种新的技术，灵感来自几何形状，这些技术可能会克服现有的技术的局限性。核心思想是研究拓扑图的最短路径距离引起的度量空间，并将算法思想从离散的几何形状转化为解决问题。除了对实际应用的潜在影响外，该项目还概述了培训研究生和本科级别的学生的具体计划；该项目的实际方面特别吸引了来自不同背景的学生。该项目还计划分发拓扑图的最新算法设计技术。该项目将重点放在两个特定的研究推力上。第一批研究图嵌入了用于设计近似算法的嵌入。这个方向的灵感来自嵌入技术对通用指标的成功。目的是通过考虑拓扑结构来发展传统度量嵌入的新放松，专门针对设计近似算法。第二个推力涉及拓扑图的不同几何结构。开发新的几何结构已导致拓扑图算法最近的突破。该项目提出了对几何结构的深入研究，包括受几何形状研究启发的各种类型的分解和尺寸。两者都很好地补充了彼此：​​了解这些结构可以洞悉构造嵌入所需的内容，反之亦然。该项目还包括许多算法问题，这些问题可以通过几何技术解决，传统技术失败。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评估标准来通过评估来获得支持的。

项目成果

Covering Planar Metrics (and Beyond): O(1) Trees Suffice

覆盖平面度量（及以上）：O(1) 棵树就足够了

• 发表时间: 2023
• 期刊: The 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023
• 作者: Chang, Hsien-Chih;Conroy, Jonathan;Le, Hung;Milenkovic, Lazar;Solomon, Shay;Than, Cuong.
• 通讯作者: Than, Cuong.