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

图是抽象对象，它对由顶点表示的实体以及由边表示的实体之间的关系进行建模。图在许多应用中都可以找到，如互联网、社交网络、交通网络、无线和传感器网络，而且它们的大小往往很大。因此，处理海量图表是当前的一项紧迫挑战。处理大规模图的一种有原则的方法是将大的输入图压缩成紧凑子图，称为扳手，这些子图将所有成对距离近似到某个用户定义的误差参数内。紧凑性加上距离保持特性，使得扳手在各种应用领域都很有用，如分布式计算、近似算法、无线网络设计、物流和规划。该项目旨在开发构造扳手的新算法，以在最基本的紧凑度度量和距离误差参数之间实现最佳折衷。除了科学目标，研究人员还包括一项教育计划，该计划利用该项目的实际相关性来吸引和培训具有不同背景的研究生和本科生。本项目侧重于两个方向。第一个方向寻求通过适用于广泛环境的统一框架来改进最先进的扳手结构。具体地说，研究人员的目标是确定在多种环境和计算模型中出现的常见技术和概念障碍，并开发通用工具和技术来解决这些障碍。这将提供理论工具，将结果从一种设置连接并传输到另一种设置。第二个方向侧重于在距离误差参数和最基本的紧凑性度量之间实现真正的最佳折衷，包括各种图族的边数和/或总边长。此外，作为这项研究的一部分，研究人员正在识别具有相似结构属性集的图族，重点关注对实际应用非常重要的图族，然后开发利用这些结构属性为这些应用提供更好扳手结构的技术。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.