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.

图是抽象对象，它对由顶点表示的实体和由边表示的实体之间的关系进行建模。图存在于许多应用中，诸如因特网、社交网络、运输网络、无线和传感器网络，并且它们通常在大小上是巨大的。因此，处理海量图形是当前的一个紧迫挑战。 处理大规模图的一个原则性方法是将大输入图压缩成紧凑的子图，称为spectum，它将所有成对距离近似到用户定义的误差参数内。空间的紧凑性，加上距离保持属性，使空间在各种应用领域，如分布式计算，近似算法，无线网络设计，物流和规划。该项目旨在开发新的算法来构建空间，实现最基本的紧凑性措施和距离误差参数之间的最佳权衡。沿着科学目标，调查者包括一个教育计划，利用这个项目的实际相关性，吸引和培养具有不同背景的研究生和本科生。该项目侧重于两个方向。第一个方向是通过一个统一的框架来改进最先进的可伸缩结构，适用于广泛的环境。具体而言，调查的目的是确定在多种设置和计算模型中出现的常见技术和概念障碍，并开发通用工具和技术来解决这些障碍。这将提供理论工具，将结果从一种设置连接和转移到另一种设置。第二个方向的重点是实现真正的最佳折衷之间的距离误差参数和最基本的紧凑性措施，包括边缘的数量和/或总的边缘长度，为各种图形的家庭。此外，作为这项研究的一部分，研究人员正在识别具有相似结构属性的图形族，重点关注对实际应用很重要的图形族，该奖项反映了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

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

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

Low Treewidth Embeddings of Planar and Minor-Free Metrics

平面和次要自由度量的低树宽嵌入

• DOI: 10.1109/focs54457.2022.00105
• 发表时间: 2022
• 期刊: The 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022
• 作者: Filtser, Arnold;Le, Hung
• 通讯作者: Le, Hung