Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths

图是顶点（点或对象）和连接顶点对的边（链接或线）的集合。图是数学对象的核心和广泛研究的类型，它们通常用于在许多不同的现实世界场景和应用程序中建模各种问题。例如，将城市中的道路网络或计算机网络或社交网络中的友谊关系建模为图形是很自然的。在无数其他场景中，一个需要解决的问题，或者一个想要研究的对象，都可以用图形自然地抽象出来。因此，为中心图问题设计有效的算法是计算机科学乃至其他领域的基础，并对计算的许多方面产生重大影响。随着应用程序需要处理的数据量的增长，确保这些算法非常快变得越来越重要。在这个项目中，研究者将在两个基本设置中研究几个中心图问题，如最大匹配、最大流量和最短路径。第一种是预先知道输入图的标准模型，其目标是为问题设计一个快速的算法，其运行时间不会显著高于读取输入所需的时间，这接近于最快的可能运行时间。第二种是动态算法模型，其中图随着时间的推移而变化（例如，考虑一个道路网络，其中计算必须考虑到道路或多或少因交通拥堵而变得拥挤），其目标是快速支持关于图的查询，例如，计算两个给定顶点之间的短路径。该项目由四个主要的相互关联的重点组成。第一个重点是动态全对最短路径（APSP）算法的设计，它可以承受自适应对手，并且在有向图和无向图中显著改善了目前已知的近似质量和运行时间之间的权衡。APSP及其变体算法通常与乘法加权更新框架结合使用，以有效地解决图中的各种流和切问题，从而提供了一个有价值且功能强大的算法工具包。第二个重点是改进和扩展已知的扩展器相关工具，这些工具通常用于设计各种图形问题的快速算法。扩展器在图算法中扮演着越来越重要的角色，这些工具可以作为许多其他图问题的构建块。第三个重点是最大匹配问题。利用受有向图中动态最短路径算法启发的技术，这部分项目的目标是为问题的二部和一般版本开发快速组合算法。最后一个重点是设计改进的算法，以维护动态图中接近最优的匹配，建立在第二和第三个重点的见解和算法的基础上。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A graph is a collection of vertices (points or objects), and a collection of edges (links or lines), that connect pairs of vertices. Graphs are a central and an extensively studied type of mathematical object, and they are commonly used to model various problems in many different real world scenarios and applications. For example, it is natural to model a road network in a city, or a computer network, or friendship relationships in a social network as a graph. There are countless other scenarios where a problem one needs to solve, or an object one desires to study, can be naturally abstracted by a graph. As a consequence, the design of efficient algorithms for central graph problems is fundamental to computer science and beyond, and has a significant impact on many aspects of computation. As the amount of data that applications need to deal with grows, it is increasingly important to ensure that such algorithms are very fast. In this project, the investigators will study several central graph problems, such as Maximum Matching, Maximum Flow, and Shortest Paths, in two basic settings. The first is the standard model where the input graph is known in advance, and the goal is to design a fast algorithm for the problem, with running time not significantly higher than the time required to read the input, which is close to the fastest possible running time. The second is the model of dynamic algorithms, where the graph changes over time (for example, consider a road network, where the computation has to account for roads becoming more or less congested with traffic), and the goal is to quickly support queries about the graph, such as, for example, computing a short path between two given vertices. This project is organized along four main interconnected thrusts. The first thrust focuses on the design of algorithms for dynamic All-Pairs Shortest Paths (APSP), that can withstand an adaptive adversary, and that significantly improve upon the currently known tradeoffs between the approximation quality and the running time, in both directed and undirected graphs. Algorithms for APSP and its variants are often used in combination with the Multiplicative Weights Update framework to efficiently solve various flow and cut problems in graphs, and thus provide a valuable and powerful algorithmic toolkit. The second thrust is directed towards improving and extending known expander-related tools that are often used in the design of fast algorithms for various graph problems. Expanders are playing an increasingly central role in graph algorithms, and these tools can serve as building blocks for many other graph problems. The third thrust focuses on the Maximum Matching problem. Using techniques inspired by algorithms for dynamic shortest path in directed graphs, the goal of this part of the project is to develop fast combinatorial algorithms for both the bipartite and the general version of the problem. The final thrust focuses on designing improved algorithms for maintaining near-optimal matchings in dynamic graphs, building on insights and algorithms developed for the second and the third thrusts.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.