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

合作研究：AF：中：（动态）匹配和最短路径的快速组合算法

• 批准号: 2402284
• 负责人: Sanjeev Khanna
• 金额: $ 59.94万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2028-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2402284&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Fast

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.

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