Efficient Distributed Approximation Algorithms

该项目的目标是在设计和分析各种重要网络优化问题的高效分布近似算法方面取得最新进展。分布式近似算法的新兴领域位于两个成熟的理论计算机科学领域的交叉点：分布式计算和近似算法。分布式近似算法权衡了分布式算法所消耗的资源量的解的最优性。除了了解分布式近似算法复杂性的基本理论兴趣外，研究分布式近似算法也有实际动机。新兴的网络技术如无线传感器网络、对等网络等都是在能量、带宽等固有的资源约束下运行的。分布式算法交换大量消息且耗时较长，会消耗较大的资源，不适用于资源受限的网络。此外，这些网络的拓扑可以动态更改。在动态设置中，通信成本和运行时间尤为重要。因此，有必要设计高效的分布式算法来解决各种通信和时间复杂度低的网络优化问题，甚至可能以降低解的质量为代价。本项目的智力优势在于开发和分析新的高效分布式近似算法来解决重要的网络优化问题，包括最小生成树和其他生成子结构、最小Steiner树及其相关问题、最短路径问题等。这些都是分布式计算中的基本问题，也是分布式通信网络中广泛使用的原语。本项目的第一部分主要针对静态网络，即拓扑不随时间变化的网络。该项目将设计和分析分布式近似算法，在给定的近似比下，在时间和消息复杂性方面提供高效的性能。这项研究的一个重要组成部分是确定适当的图参数，以捕捉手头问题的分布式复杂性。这些参数是自然的下界，有助于最优算法的设计。该项目的主要目标是开发统一的方法来为各种问题设计高效的分布式近似算法。项目的第二部分集中于动态网络的分布式算法的设计和分析，即拓扑动态变化的网络。其目的是研究高效的分布式动态算法来构造和维护重要的生成子结构问题的近最优解。这些算法将利用局部性，并将被设计成在动态网络模型上很好地工作。该项目的更广泛的影响是潜在地影响新兴通信网络中的算法设计，特别是传感器网络和对等网络。该项目将产生高效和可扩展的分布式算法，并提供可证明的性能保证。PI将与应用研究人员合作，最大限度地将理论结果应用于实际应用。拟议的研究是理论继续产生实践影响的一个很好的机会，也是对算法和网络课程的宝贵补充。PI将开发一门与该研究密切相关的关于分布式近似算法的新课程。该课程还将有助于向更广泛的受众传播这项研究所需的数学工具和技术。PI的研究小组网络算法和分析实验室将培训研究生和本科生处理分布式网络中出现的各种算法问题，强调在设计高效的分布式算法时使用随机化，以及网络的概率建模和分析。

The goal of this project is to advance the state of the art in the design and analysis of efficient distribution approximation algorithms for various important network optimization problems. The emerging area of distributed approximation algorithms lies at the intersection of two well-established theoretical computer science areas: distributed computing and approximation algorithms. Distributed approximation algorithms tradeoff optimality of the solution for the amount of resources consumed by the distributed algorithm. Besides a fundamental theoretical interest in understanding the algorithmic complexity of distributed approximation, there is also a practical motivation in studying distributed approximation algorithms. Emerging networking technologies such as ad hoc wireless sensor networks and peer-to-peer networks operate under inherent resource constraints such as energy, bandwidth etc. A distributed algorithm which exchanges a large number of messages and takes a lot of time can consume a relatively large amount of resources, and is not suitable in a resource-constrained network. Also, the topology of these networks can change dynamically. Communication cost and running time is especially crucial in a dynamic setting. Hence it becomes necessary to design efficient distributed algorithms for various network optimization problems that have low communication and time complexity, even possibly at the cost of a reduced quality of solution.The intellectual merit of this project lies in the development and analysis of new efficient distributed approximation algorithms for important network optimization problems including the minimum spanning tree and other spanning substructures, the minimum Steiner tree and related problems, the shortest paths problem etc. These are fundamental problems in distributed computing and are widely used primitives in distributed communication networks.The first part of the project focuses on static networks, i.e., networks whose topology doesn't change with time. The project will design and analyze distributed approximation algorithms that give efficient performance, in terms of both time and message complexity, for a given approximation ratio. An important ingredient of the research is identifying appropriate graph parameters that capture the distributed complexity of the problem at hand. Such parameters serve as natural lower bounds and facilitate the design of optimal algorithms. An overarching goal is to develop uniform approaches to design efficient distributed approximation algorithms for a wide variety of problems.The second part of the project focuses on design and analysis of distributed algorithms for dynamic networks, i.e., networks whose topology changes dynamically. The goal is to study efficient distributed dynamic algorithms to construct and maintain near-optimal solutions for important spanning substructure problems. The algorithms will exploit locality and will be designed to work well on dynamic network models.The broader impact of this project is the potential to impact algorithm design in emerging communication networks, in particular, sensor networks and peer-to-peer networks. The project will yield efficient and scalable distributed algorithms with provable performance guarantees. The PI will collaborate with applied researchers to maximize the impact of the theoretical results to practical applications. The proposed research is a great opportunity for theory to continue to have a practical impact, and a valuable addition to the curricula in both algorithms and networks. The PI will develop a new course on distributed approximation algorithms that is closely related to the research. The course will also aid in disseminating mathematical tools and techniques needed for this research to a wider audience. The PI's research group, Network Algorithms and Analysis Laboratory, will train both graduate and undergraduate students to tackle a variety of algorithmic problems that arise in distributed networks, emphasizing use of randomization in designing efficient distributed algorithms, and probabilistic modeling and analysis of networks.