BSF:2012338:Shortest Paths: Upper and lower bounds

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

• 批准号: 1417238
• 负责人: Virginia Williams
• 金额: $ 4.5万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1417238&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）共同支持美国和以色列研究人员之间的合作。现代世界的许多重要问题都可以通过在一些网络中找到最短路径来解决。一些示例包括计算道路网络中从一个城市到另一个城市的驾驶方向，或者在诸如互联网的通信网络中将互联网流量从一台计算机路由到另一台计算机。这些应用中的网络不仅复杂，而且可能非常庞大。 因此，开发快速、可靠和可扩展的最短路径算法至关重要。 提出的研究的主要目标是提供这样的算法在各种设置，提供数学保证其性能和scalability.The研究将集中在两个概念的数据结构保持最短路径，都集中在存储距离信息使用小的空间。第一种是距离预言机（Distance oracles，DO），它是一种数据结构，它可以完整地表示网络的路径结构，并能够快速检索任意两个给定节点之间的近似距离和最短路径。研究的目的是加深我们对DO的理解，在几个不同的方式：通过获得DO与改进的保证，在新的（如分布式）设置，通过开发更快的算法来构建DO，并通过证明有条件的，或最好是无条件的细胞探测下界表明，所获得的保证基本上是最优的。 第二种类型的最短路径数据结构将被考虑是距离敏感性神谕（DSO）。这些数据结构提供了图中距离的紧凑表示，其中边可能变得不可用。对DSO的查询由一个故障边和两个节点（源和目标）组成，并且DSO必须返回从源到目标的不使用故障边的最短路径。这里的目标是开发更快的算法来构建具有快速查询时间的DSO，并证明DSO与其他密切相关的问题（例如全对最短路径）之间的关系。除了其内在价值外，DSO还可以帮助开发高效的动态最短路径算法，这是本项目的另一个目标。除了项目背后明确的实际动机外，所要研究的问题与数学中的许多概念（度量嵌入，图和几何空间等）有着有趣的关系。因此，这项研究的影响超出了计算机科学的严格界限。 PI全心全意地致力于多样性。PI在招募和指导少数民族学生方面有经验，并将继续积极寻找和招募来自不同文化和背景的学生。