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

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

基本信息

  • 批准号:
    2129139
  • 负责人:
  • 金额:
    $ 50万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-06-01 至 2024-05-31
  • 项目状态:
    已结题

项目摘要

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的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(14)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
列出、验证和计算 DAG 中的最低共同祖先:算法和细粒度下界
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mathialagan, Surya;Vassilevska Williams, Virginia;Xu, Yinzhan
  • 通讯作者:
    Xu, Yinzhan
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
更快的单调最小加产品、范围模式和单一来源替换路径
  • DOI:
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Gu, Yuzhou;Polak, Adam;Vassilevska Williams, Virginia;Xu, Yinzhan
  • 通讯作者:
    Xu, Yinzhan
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
列出可避免顶点的新下界和上限
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure
多边故障下替换路径的算法和下界
New Additive Approximations for Shortest Paths and Cycles
最短路径和周期的新加法近似
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Deng, Mingyang;Kirkpatrick, Yael;Rong, Victor;Vassilevska Williams, Virginia;Zhong, Ziqian
  • 通讯作者:
    Zhong, Ziqian
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Virginia Williams其他文献

408 ACCURACY OF CONTEMPORARY PROSTATE CANCER STAGING DATA IN THE NEW MEXICO TUMOR REGISTRY: IMPLICATIONS FOR STUDIES THAT UTILIZE SEER
  • DOI:
    10.1016/j.juro.2010.02.477
  • 发表时间:
    2010-04-01
  • 期刊:
  • 影响因子:
  • 作者:
    Satyan Shah;Anthony Smith;Virginia Williams;Charles Wiggins
  • 通讯作者:
    Charles Wiggins
Naloxone reversal of mild neurobehavioral depression in normal newborn infants after routine obstetric analgesia
  • DOI:
    10.1016/s0022-3476(79)80369-8
  • 发表时间:
    1979-01-01
  • 期刊:
  • 影响因子:
  • 作者:
    Bedford W. Bonta;Jeryl V. Gagliardi;Virginia Williams;Joseph B. Warshaw
  • 通讯作者:
    Joseph B. Warshaw
A systematic comparison of two-equation Reynolds-averaged Navier–Stokes turbulence models applied to shock–cloud interactions
应用于冲击云相互作用的两个方程雷诺平均纳维-斯托克斯湍流模型的系统比较
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Matthew D. Goodson;F. Heitsch;Karl Eklund;Virginia Williams
  • 通讯作者:
    Virginia Williams
NALOXONE REVERSAL OF MILD NEUROBEHAVIORAL DEPRESSION IN NORMAL NEWBORNS AFTER ROUTINE OBSTETRICAL ANALGESIA
  • DOI:
    10.1203/00006450-197704000-00091
  • 发表时间:
    1977-04-01
  • 期刊:
  • 影响因子:
    3.100
  • 作者:
    Virginia Williams;Bedford W Bonta;Jeryl V Gagliardi;Joseph B Warshaw
  • 通讯作者:
    Joseph B Warshaw

Virginia Williams的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Virginia Williams', 18)}}的其他基金

AF:Small: Algorithms and Limitations for Matrix Multiplication
AF:Small:矩阵乘法的算法和限制
  • 批准号:
    2330048
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
NSF Student Travel Grant for 2019 Theoretical Computer Science (TCS) Women Meeting at Symposium on Theory of Computing (STOC)
NSF 学生旅费补助金用于 2019 年理论计算机科学 (TCS) 女性在计算理论研讨会 (STOC) 上的会议
  • 批准号:
    1931307
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Small: Average-Case Fine-Grained Complexity
AF:小:平均情况的细粒度复杂性
  • 批准号:
    1909429
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Small: Graphs and structures for distance estimation
AF:小:用于距离估计的图形和结构
  • 批准号:
    1740525
  • 财政年份:
    2017
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Medium: Collaborative Research: Hardness in Polynomial Time
AF:媒介:协作研究:多项式时间内的硬度
  • 批准号:
    1740519
  • 财政年份:
    2017
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
CAREER:Matrix Products: Algorithms and Applications
职业:矩阵产品:算法和应用
  • 批准号:
    1651838
  • 财政年份:
    2017
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
BSF:2012338:Shortest Paths: Upper and lower bounds
BSF:2012338:最短路径:上限和下限
  • 批准号:
    1740501
  • 财政年份:
    2017
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Medium: Collaborative Research: Hardness in Polynomial Time
AF:媒介:协作研究:多项式时间内的硬度
  • 批准号:
    1514339
  • 财政年份:
    2015
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
AF: Small: Graphs and structures for distance estimation
AF:小:用于距离估计的图形和结构
  • 批准号:
    1528078
  • 财政年份:
    2015
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
EAGER: Formal models of intention
EAGER:意图的正式模型
  • 批准号:
    1347214
  • 财政年份:
    2013
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了