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

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

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.