AF: Small: Distributed Algorithms for Near-Planar Networks

该项目的目标是开发一个算法工具箱，为平面和近平面网络设计高效的分布式算法。（非正式地说，平面网络是可以在二维平面上绘制而不需要任何线交叉的网络。）许多现实世界的网络和优化问题实例都有一个接近平面的结构，允许更简单、更有效、通常更实用的算法。对这种网络结构及其算法含义的研究是一项非常成功的努力，它具有丰富的理论、许多通用的工具、显著的算法进步，以及对感兴趣的问题实例的显著性能改进。虽然现代系统变得越来越大，越来越分布式，但人们对如何在近平面实例上改进分布式算法知之甚少。本项目旨在改变这一点，并为分布式环境带来类似的改进。虽然其范围主要是理论性的，但要开发的算法和一般原则具有为具有现实世界影响的实际算法奠定基础的潜力。该项目还将产生广泛的教育影响。大部分研究将由研究生完成或与研究生合作完成。此外，所提出的研究方向有许多理论问题，适合没有广泛背景知识的本科生，并提供实验和实施项目的机会。最后，该问题的跨学科性质可能会促进PI与不同领域的其他研究人员之间的许多合作。开发的任何工具和算法都将公开共享。该项目将启动平面和近平面网络分布式算法的原则性研究。特别是对于直径为D、标准带宽限制的网络（CONGEST模型），该项目旨在获得以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.