BSF:2012338:Shortest Paths: Upper and lower bounds

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

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.