Efficient Distributed Approximation Algorithms

这个项目的目标是推进各种重要网络优化问题的有效分布近似算法的设计和分析的最新水平。分布式近似算法的新兴领域位于两个成熟的理论计算机科学领域的交叉点：分布式计算和近似算法。 分布式近似算法权衡了分布式算法消耗的资源量的解决方案的最优性。 除了理解分布式近似算法复杂性的基本理论兴趣之外，研究分布式近似算法也有实际动机。 新兴的网络技术，如ad hoc无线传感器网络和对等网络运行在固有的资源限制，如能源，带宽等分布式算法，交换大量的消息，并需要大量的时间可以消耗相对大量的资源，是不适合在资源受限的网络。 此外，这些网络的拓扑结构可以动态地改变。 通信成本和运行时间在动态环境中尤其重要。 因此，有必要为各种网络优化问题设计有效的分布式算法，这些问题具有低通信和时间复杂性，甚至可能以降低解的质量为代价。本项目的智力价值在于开发和分析新的有效分布式近似算法，用于重要的网络优化问题，包括最小生成树和其他生成子结构，最小Steiner树及其相关问题，最短路径问题等。这些都是分布式计算中的基本问题，也是分布式通信网络中广泛使用的原语。本项目的第一部分集中于静态网络，即，拓扑结构不随时间变化的网络。 该项目将设计和分析分布式近似算法，提供有效的性能，在时间和消息的复杂性，对于一个给定的近似比。 这项研究的一个重要组成部分是确定适当的图形参数，捕捉手头问题的分布式复杂性。这样的参数作为自然的下限，并促进最优算法的设计。一个首要目标是开发统一的方法来设计有效的分布式近似算法，用于各种各样的问题。该项目的第二部分侧重于动态网络的分布式算法的设计和分析，即，拓扑结构动态变化的网络。 我们的目标是研究有效的分布式动态算法，以构建和维护重要的跨越子结构问题的近优解。 该算法将利用局部性，并将被设计为在动态网络models.The更广泛的影响，这个项目是影响新兴的通信网络，特别是传感器网络和对等网络的算法设计的潜力。 该项目将产生高效和可扩展的分布式算法，具有可证明的性能保证。 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.