Efficient Distributed Approximation Algorithms

高效的分布式逼近算法

• 批准号: 0830476
• 负责人: Gopal Pandurangan
• 金额: $ 10万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2010-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830476&HistoricalAwards=false
• 关键词: Efficient; Distributed; Approximation; Algorithms

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.

该项目的目的是在设计和分析各种重要网络优化问题的有效分布近似算法的设计和分析中促进艺术的状态。分布式近似算法的新兴领域位于两个良好的理论计算机科学领域的交集：分布式计算和近似算法。 分布式近似算法权衡最佳解决方案对分布式算法消耗的资源量的最优性。 除了理解分布式近似的算法复杂性的基本理论兴趣外，研究分布式近似算法也有实际动机。 在固有的资源限制（例如能源，带宽等）下运行的新兴网络技术，例如临时无线传感器网络和点对点网络，分布式算法可以交换大量消息，并且需要大量时间可以消耗相对较大的资源，并且不适合在资源限制的网络中。 同样，这些网络的拓扑可以动态变化。 在动态环境中，沟通成本和运行时间尤为重要。 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在分布式计算中，是分布式通信网络中广泛使用的原始方法。项目的第一部分着重于静态网络，即，其拓扑不会随时间而变化的网络。 该项目将设计和分析分布式的近似算法，以给定的近似比，从时间和消息复杂性方面具有有效的性能。 研究的重要成分是确定适当的图参数，以捕获当前问题的分布式复杂性。此类参数是自然的下限，并促进了最佳算法的设计。一个总体目标是开发统一的方法来设计有效的各种问题的有效分布式近似算法。项目的第二部分着重于设计和分析动态网络的分布式算法，即拓扑动态变化的网络。 目的是研究有效的分布式动态算法，以构建和维护近乎最佳的解决方案，以解决重要的跨越子结构问题。 该算法将利用局部性，并将旨在在动态网络模型上工作。该项目的更广泛影响是影响新兴通信网络（尤其是传感器网络和对等网络）中算法设计的潜力。 该项目将产生具有可证明性能保证的高效且可扩展的分布式算法。 PI将与应用研究人员合作，以最大程度地提高理论结果对实际应用的影响。拟议的研究是理论继续产生实际影响的绝佳机会，并且在算法和网络中对课程的宝贵补充。 PI将开发与分布式近似算法的新课程，该课程与研究密切相关。 该课程还将有助于将本研究所需的数学工具和技术传播给更广泛的受众。 PI的研究小组，网络算法和分析实验室将培训研究生和本科生，以解决分布式网络中出现的各种算法问题，强调在设计有效的分布式算法时使用随机化，以及网络的概率建模和分析。