BSF:2012338:Shortest Paths: Upper and lower bounds

BSF:2012338:最短路径：上限和下限

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

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. Through this program, NSF and the United States - Israel Binational Science Foundation (BSF) jointly support collaborations among US-based researchers and Israel-based researchers.Many important problems in the modern world can be solved by finding shortest paths in some network. Some examples include computing driving directions from one city to another in a road network, or routing internet traffic from one computer to another in a communication network such as the internet. The networks in such applications are not only complex, but can also be extremely large. The development of fast, reliable and scalable algorithms for shortest paths is thus of crucial importance. The major goal of the proposed research is to provide such algorithms in a variety of settings, providing mathematical guarantees on their performance and scalability.The research will focus on two notions of data structures maintaining shortest paths, both focusing on storing distance information using small space. The first are Distance oracles (DOs), data structures that compactly represent the path structure of a network with the ability to quickly retrieve approximate distances and shortest paths between any two given nodes. The research aims at deepening our understanding of DOs in several different ways: by obtaining DOs with improved guarantees in new (e.g. distributed) settings, by developing faster algorithms for constructing DOs, and by proving conditional, or preferably unconditional cell-probe lower bounds showing that the obtained guarantees are essentially optimal. The second type of shortest paths data structures that will be considered are Distance sensitivity oracles (DSOs). These are data structures that provide a compact representation of the distances in a graph in which edges can become unavailable. A query to a DSO consists of a failed edge and two nodes, a source and a target, and the DSO must return a shortest path from the source to the target that does not use the failed edge. The goal here is to develop faster algorithms for constructing DSOs with fast query times, and to prove relationships between DSOs and other closely related problems such as all-pairs shortest paths. In addition to their intrinsic value, DSOs may also help develop efficient dynamic shortest paths algorithms which is another objective of this project.Besides the clear practical motivation behind the project, the problems to be studied have intriguing relations to many concepts in mathematics (metric embeddings, graph and geometric spanners, etc). Thus the impact of this research goes beyond the strict boundaries of computer science. The PI is whole-heartedly committed to diversity. The PI has experience in recruiting and mentoring minority students, and will continue to take an active role in seeking and recruiting students from diverse cultures and backgrounds.

该项目是美国-以色列计算机科学合作（USICCS）计划的一部分。通过这个项目，NSF和美国-以色列两国科学基金会（BSF）共同支持美国科学家和以色列科学家之间的合作。现代世界中许多重要的问题都可以通过在某些网络中寻找最短路径来解决。一些例子包括在道路网络中计算从一个城市到另一个城市的驾驶方向，或者在通信网络（如互联网）中将互联网流量从一台计算机路由到另一台计算机。这种应用程序中的网络不仅复杂，而且可能非常大。因此，开发快速、可靠和可扩展的最短路径算法至关重要。提出的研究的主要目标是在各种设置中提供这样的算法，为其性能和可扩展性提供数学保证。研究将集中在两个保持最短路径的数据结构概念上，这两个概念都侧重于使用小空间存储距离信息。第一种是距离预言器（DOs），这种数据结构简洁地表示网络的路径结构，具有快速检索任意两个给定节点之间的近似距离和最短路径的能力。该研究旨在通过几种不同的方式加深我们对DOs的理解：通过在新的（例如分布式）设置中获得具有改进保证的DOs，通过开发更快的构造DOs的算法，以及通过证明条件，或者最好是无条件的细胞探针下界来表明所获得的保证本质上是最优的。要考虑的第二种最短路径数据结构是距离敏感性预言器（dso）。这些数据结构提供了图中距离的紧凑表示，其中边可能不可用。对DSO的查询由一个失败的边缘和两个节点组成，一个源和一个目标，DSO必须返回从源到目标的最短路径，该路径不使用失败的边缘。这里的目标是开发更快的算法，用于构建查询时间更快的dso，并证明dso与其他密切相关的问题（如全对最短路径）之间的关系。除了其内在价值之外，dso还可以帮助开发高效的动态最短路径算法，这是本项目的另一个目标。除了项目背后明确的实际动机外，要研究的问题与许多数学概念（度量嵌入，图形和几何扳手等）有着有趣的关系。因此，这项研究的影响超出了计算机科学的严格界限。PI全心全意地致力于多样性。PI在招收和指导少数民族学生方面有经验，并将继续在寻找和招收来自不同文化和背景的学生方面发挥积极作用。