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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*

平面和无次要度量嵌入到多对数树宽度量中，预期乘性失真任意接近 1*

• 发表时间: 2023
• 期刊: IEEE Annual Symposium on Foundations of Computer Science
• 作者: Vincent Cohen;Hung Le;Marcin Pilipczuk;Michal Pilipczuk
• 通讯作者: Michal Pilipczuk

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.