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

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

• 批准号: 2402283
• 负责人: Julia Chuzhoy
• 金额: $ 59.93万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2028-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2402283&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 的法定使命，并通过使用基金会的评估进行评估，被认为值得支持。智力价值和更广泛的影响审查标准。