NSF-BSF: Small: AF: Towards a Unified Theory of Spanners

NSF-BSF：小：AF：迈向扳手的统一理论

• 批准号: 2121952
• 负责人: Hung Le
• 金额: $ 50万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2121952&HistoricalAwards=false
• 关键词: NSF; BSF; Small; AF; Towards

Graphs are abstract objects that model entities, represented by vertices, and relationships between them, represented by edges. Graphs are found in numerous applications, such as the Internet, social networks, transportation networks, wireless and sensor networks, and they are often massive in size. Accordingly, coping with massive graphs is a pressing challenge of the current time. A principled approach for dealing with massive graphs is to compress big input graphs into compact subgraphs, called spanners, that approximate all pairwise distances to within some user-defined error parameter. The compactness, coupled with distance-preserving properties, make spanners useful in various application domains, such as distributed computing, approximation algorithms, wireless network design, logistics and planning. This project aims to develop new algorithms for constructing spanners that achieve optimal trade-offs between the most fundamental compactness measures and the distance error parameter. Along with the scientific goals, the investigator includes an education plan that takes advantage of the practical relevance of this project to attract and train graduate and undergraduate students with diverse backgrounds. This project focuses on two directions. The first direction seeks to improve the state-of-the-art spanner constructions via a unified framework, applicable to a wide range of settings. Specifically, the investigator aims at identifying common technical and conceptual barriers arising in multiple settings and computational models, and developing general tools and techniques to address these barriers. This will provide theoretical tools to connect and transfer results from one setting to another. The second direction focuses on achieving truly optimal tradeoffs between the distance error parameter and the most fundamental compactness measures, including the number of edges and/or total edge length, for various graph families. Moreover, as part of this research, the investigator is identifying graph families that share similar sets of structural properties, focusing on graph families that are important for practical applications, and then developing techniques that exploit such structural properties to provide better spanner constructions for these applications.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.

图是图表的抽象对象，该对象模拟了以顶点为代表的实体及其之间的关系，以边缘为代表。在许多应用程序中找到图形，例如Internet，社交网络，运输网络，无线和传感器网络，并且它们的规模通常很大。因此，应对大量图是当前时间的紧迫挑战。 处理大量图的原则方法是将大输入图压缩为紧凑的子图，称为Spanners，将所有成对距离近似于某些用户定义的错误参数。紧凑性，再加上远距离的属性，使跨度在各种应用程序域中有用，例如分布式计算，近似算法，无线网络设计，物流和计划。该项目旨在开发新的算法来构建跨度，以在最基本的紧凑度措施和距离误差参数之间实现最佳的权衡。除了科学目标外，研究人员还包括一项教育计划，该计划利用该项目的实际相关性吸引和培训具有不同背景的毕业生和本科生。该项目侧重于两个方向。第一个方向旨在通过统一的框架来改善最新的扳手构造，适用于广泛的设置。具体而言，研究人员旨在确定在多种环境和计算模型中产生的常见技术和概念障碍，并开发通用工具和技术来解决这些障碍。这将提供理论工具将结果从一个设置连接和传输到另一种设置。第二个方向的重点是在距离误差参数和最基本的紧凑度度量（包括边缘数量和/或总边长度）之间实现真正的最佳权衡。此外，作为这项研究的一部分，研究者正在确定具有相似结构特性集的图形家族，重点关注对实际应用至关重要的图形家族，然后开发利用这种结构性属性来为这些应用提供更好的跨度结构的技术。该奖项通过评估了NSF的法规范围，反映了通过评估范围的范围，该奖项反映了该奖项的知识范围，该奖项已被评估范围众所周知的范围。

项目成果

Dynamic Matching Algorithms Under Vertex Updates

顶点更新下的动态匹配算法

• DOI: 10.4230/lipics.itcs.2022.96
• 发表时间: 2022
• 期刊: The 13th Innovations in Theoretical Computer Science Conference (ITCS 2022
• 作者: Le, Hung;Milenkovic, Lazar;Solomon, Shay;Vassilevska Williams, Virginia
• 通讯作者: Vassilevska Williams, Virginia

Locality-Sensitive Orderings and Applications to Reliable Spanners

区域敏感的排序和可靠 Spanner 的应用

• DOI: 10.1145/3519935.3520042
• 发表时间: 2022
• 期刊: The 54th Annual ACM Symposium on Theory of Computing (STOC 2022
• 作者: Filtser, Arnold;Le, Hung
• 通讯作者: Le, Hung

Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

（近）线性时间内一般图的近最优 Spanner

• DOI: 10.1137/1.9781611977073.132
• 发表时间: 2022
• 期刊: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Le, Hung;Solomon, Shay
• 通讯作者: Solomon, Shay

Optimal Approximate Distance Oracle for Planar Graphs

平面图的最佳近似距离预言机

• DOI: 10.1109/focs52979.2021.00044
• 发表时间: 2022
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science
• 作者: Le, Hung;Wulff-Nilsen, Christian
• 通讯作者: Wulff-Nilsen, Christian

Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners

只见树木，不见森林：通过有界跳跃直径扳手在度量空间中导航

• DOI: 10.1145/3519270.3538414
• 发表时间: 2022
• 期刊: The 41st ACM Symposium on Principles of Distributed Computing (PODC 2022
• 作者: Kahalon, Omri;Le, Hung;Milenković, Lazar;Solomon, Shay
• 通讯作者: Solomon, Shay