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

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

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.