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-Hard问题时，人们可以求助于启发式或近似法，但很可能不可能找到一个适用于所有情况的多项式时间算法。使用细粒度复杂性的技术，这个项目可以对许多科学学科的研究人员如何看待他们需要的多项式时间基元产生类似的广泛影响。细粒度的复杂性可以为为什么他们的计算问题似乎被困在二次或三次时间障碍上提供一个强有力的解释，并指出必须驳斥的特定难度猜想才能打破这些障碍。这一奖项反映了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