AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate

AF：小：最短路径和距离参数：更快、容错且更准确

• 批准号: 2129139
• 负责人: Virginia Williams
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2129139&HistoricalAwards=false
• 关键词: AF; Small; Shortest; Paths; Distance

What do the following have in common: sending an email, planning a road trip using GPS software, robot motion planning, uncovering structure in biological regulatory networks and measuring the spread of information in social networks? The answer is: they all necessitate the computation of shortest paths. Efficiently computing shortest paths is among the oldest and most well-studied problems in computer science, with myriads of applications. Many ways to find shortest paths in networks have been designed over the last several decades, with various guarantees on their speed. How fast a shortest paths algorithm runs depends on the size of the network it is run on. In today's world of big data, what was considered fast in the past may no longer be, and new faster algorithms are needed. In many applications it is better to be fast than accurate, so that fast algorithms that obtain paths that are almost (but not quite) shortest are often desired. Real world networks are also dynamic rather than static: roads can become unavailable due to construction or traffic, network links on the internet can go down, and friendship links in social networks can appear and disappear. Shortest paths algorithms need to be able to handle the dynamic nature of the networks they run on. To this end, this project considers the computation of shortest paths and a variety of shortest paths parameters, considering trade-offs between speed and accuracy, preparing for network changes, and proving tight guarantees on the performance of the algorithms.This project focuses on developing algorithms for classical computer science problems such as All-Pairs Shortest Paths (APSP), Replacement Paths, graph Diameter and Radius and Betweenness centrality, in various settings. APSP in graphs on n vertices and arbitrary edge weights, can be solved exactly in time which is cubic in n. Slightly faster algorithms are known, but none run substantially faster than cubic time. Cubic time is completely impractical for any modern application, unfortunately, and it is widely believed that APSP does not admit a substantially faster algorithm that works for all graphs. One of the goals of this project is to determine when faster algorithms for APSP are possible. For instance, what restrictions on the input graphs allow for faster APSP? What kinds of approximation guarantees are achievable with fast algorithms? The project asks similar questions for the other problems of study. In addition, it considers ways to deal with the dynamic nature of graphs. One way is to construct distance sensitivity oracles: data structures that store a graph, and support shortest paths queries while also allowing for a small number of edges of the graph to be updated for each query. The project considers the tradeoffs between speed, accuracy and the number of edge faults that will be supported. Finally, the project also focuses on proving limitations on how fast computers can solve the problems of interest, using fine-grained complexity. Nearly all scientists using computational methods appreciate the implications of NP-hardness on their work. When faced with an NP-hard problem, one can resort to heuristics or approximation, but it is likely impossible to find a polynomial-time algorithm that works for all instances. Using techniques from fine-grained complexity, this project can have a similarly broad impact on how researchers across many scientific disciplines view the polynomial-time primitives they need. Fine-grained complexity can offer a powerful explanation for why their computational problems seem to be "stuck" at a quadratic- or cubic-time barrier, and point to specific hardness conjectures that must be refuted to break those barriers.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.

以下这些有什么共同点：发送电子邮件，使用GPS软件规划公路旅行，机器人运动规划，揭示生物调节网络的结构以及测量社交网络中的信息传播？答案是：它们都需要计算最短路径。有效地计算最短路径是计算机科学中最古老、研究最充分的问题之一，有着无数的应用。在过去的几十年里，人们设计了许多在网络中寻找最短路径的方法，并对它们的速度有各种保证。最短路径算法的运行速度取决于它所运行的网络的大小。在今天的大数据世界中，过去被认为是快速的算法可能不再是，需要新的更快的算法。在许多应用中，快速比准确更好，因此通常需要获得几乎（但不完全）最短路径的快速算法。真实的世界网络也是动态的，而不是静态的：道路可能由于施工或交通而变得不可用，互联网上的网络链接可能会中断，社交网络中的友谊链接可能会出现和消失。最短路径算法需要能够处理其所运行的网络的动态特性，为此，本项目考虑了最短路径的计算和各种最短路径参数，考虑速度和精度之间的权衡，为网络变化做好准备，并证明算法性能的严格保证。该项目的重点是开发经典计算机科学问题的算法，所有对最短路径（APSP），替换路径，图形直径和半径和介数中心，在各种设置。在n阶任意边权的图中，APSP可以在时间上精确求解，时间是n的三次。稍快的算法是已知的，但没有一个运行速度比立方时间快得多。不幸的是，立方时间对于任何现代应用都是完全不切实际的，并且人们普遍认为APSP不承认适用于所有图的更快算法。该项目的目标之一是确定何时可以实现更快的APSP算法。例如，对输入图形的哪些限制允许更快的APSP？什么样的近似保证是可实现的快速算法？该项目对其他研究问题提出了类似的问题。此外，它考虑了处理图形动态性质的方法。一种方法是构建距离敏感性预言机：存储图的数据结构，并支持最短路径查询，同时还允许为每个查询更新图的少量边。该项目考虑了速度、精度和支持的边缘故障数量之间的权衡。最后，该项目还专注于证明计算机使用细粒度复杂性解决感兴趣问题的速度的局限性。几乎所有使用计算方法的科学家都认识到NP困难对他们工作的影响。当面对NP难问题时，人们可以求助于算法或近似，但很可能不可能找到适用于所有情况的多项式时间算法。使用细粒度复杂性的技术，该项目可以对许多科学学科的研究人员如何看待他们所需要的多项式时间原语产生类似的广泛影响。细粒度的复杂性可以提供一个强有力的解释，为什么他们的计算问题似乎是“卡”在一个二次或二次时间的障碍，并指出特定的硬度假设，必须驳斥，以打破这些障碍。这个奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

项目成果

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

列出、验证和计算 DAG 中的最低共同祖先：算法和细粒度下界

• 发表时间: 2022
• 期刊: and Programming (ICALP 2022
• 作者: Mathialagan, Surya;Vassilevska Williams, Virginia;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

更快的单调最小加产品、范围模式和单一来源替换路径

• 发表时间: 2021
• 期刊: and Programming (ICALP 2021
• 作者: Gu, Yuzhou;Polak, Adam;Vassilevska Williams, Virginia;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

列出可避免顶点的新下界和上限

• 发表时间: 2022
• 期刊: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022
• 作者: Deng, Mingyang;Vassilevska Williams, Virginia;Zhong, Ziqian
• 通讯作者: Zhong, Ziqian

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure

多边故障下替换路径的算法和下界

• DOI: 10.1109/focs54457.2022.00090
• 发表时间: 2022
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Williams, Virginia Vassilevska;Woldeghebriel, Eyob;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan

New Additive Approximations for Shortest Paths and Cycles

最短路径和周期的新加法近似

• 发表时间: 2022
• 期刊: and Programming (ICALP 2022
• 作者: Deng, Mingyang;Kirkpatrick, Yael;Rong, Victor;Vassilevska Williams, Virginia;Zhong, Ziqian
• 通讯作者: Zhong, Ziqian