AF: Small: Distributed Algorithms for Near-Planar Networks

这个项目的目标是开发一个算法工具箱，为平面和近平面网络设计高效的分布式算法。(非正式地说，平面网络是指可以在二维表面上绘制的网络，而不会有任何线条相交。)许多现实世界的网络和优化问题实例都具有接近平面的结构，允许使用更简单、更高效且通常更实用的算法。对这种网络结构及其算法含义的研究已经是一项非常成功的努力，拥有丰富的理论、许多通用的工具、显著的算法进步以及在感兴趣的问题实例上的显著性能改进。虽然现代系统变得越来越大，越来越分布式，但人们对如何在近平面实例上改进分布式算法知之甚少。该项目旨在改变这一点，并为分布式环境带来类似的改进。虽然它的范围主要是理论上的，但要开发的算法和一般原理有可能为具有现实世界影响的实际算法奠定基础。该项目还将产生广泛的教育影响。大部分研究将由研究生或与研究生合作完成。此外，提出的研究方向具有许多适合于背景知识较少的本科生的理论问题，也为实验和实施项目提供了机会。最后，这个问题的跨学科性质可能会促进PI和不同领域的其他研究人员之间的许多合作。开发的任何工具和算法都将公开共享。该项目将启动平面和近平面网络的分布式算法的原则性研究。特别是，对于直径D和标准带宽限制(拥塞模型)的网络，该项目旨在获得高效的分布式算法，运行在O(D)个同步轮次中，用于重要的标准优化问题，如最大流、最小生成树和各种最短路径问题。这种方法非常及时地联系到了最近广泛分布的下界，这些下界表明在一般(稀疏)图中，许多优化问题不能在少于Omega(Sqrt(N))轮的时间内计算，甚至不能粗略地近似。PI认为，这一建议为分布式网络优化算法的理论提供了一个令人振奋的新方向，并为平面和近平面图的算法研究提供了一个新的视角。我们期望这个更广阔的研究方向和这项计划所产生的具体初步结果，会引起社会人士的兴趣，并为更大范围和更广泛的调查奠定基础。

The goal of this project is the development of an algorithmic toolbox to design efficient distributed algorithms for planar and near-planar networks. (Informally, a planar network is one that can be drawn on a two-dimensional surface without any lines crossing.) Many real-world networks and optimization problem instances have a near-planar structure that allows for simpler, more efficient, and often more practical algorithms. The study of such network structures and their algorithmic implications has been a very successful endeavor with a rich theory, many versatile tools, significant algorithmic advances, and drastic performance improvements on problem instances of interest. While modern systems become increasingly larger and more distributed, little is known about how distributed algorithms can be improved on near-planar instances. This project aims to change this and to bring similar improvements to the distributed setting. While its scope is primarily theoretical, the algorithms and general principles to be developed have the potential of laying the groundwork for practical algorithms with real-world impacts. The project will also have a broad educational impact. Much of the research will be done by or in collaboration with graduate students. Furthermore, the proposed research direction features many theoretical questions suitable for undergraduate students without extensive background knowledge and also provides opportunities for experiments and implementation projects. Lastly, the interdisciplinary nature of the problem will likely foster many collaborations between the PI and other researchers in different fields. Any tools and algorithms developed will be shared publicly.This project will initiate the principled study of distributed algorithms for planar and near-planar networks. In particular, for networks with diameter D and standard bandwidth-limitations (CONGEST model), the project aims at obtaining efficient distributed algorithms running in O(D) synchronous rounds for important standard optimization problems like maximum flow, minimum spanning tree, and various shortest path problems. This approach very timely connects to recent, far-reaching, distributed lower bounds which show that in general (sparse) graphs many optimization problems cannot be computed or even crudely approximated in less than Omega(sqrt(n))-rounds. The PI believes that this proposal provides an exciting new direction for the theory of distributed network optimization algorithms and gives a new perspective on the algorithmic study of planar and near-planar graphs. The expectation is that this broader research direction and the concrete initial results coming out of this project will spark the interest of the community and serve as a basis for a larger and more extensive investigation.