Efficient Distributed Approximation Algorithms

高效的分布式逼近算法

• 批准号: 1023166
• 负责人: Eli Upfal
• 金额: --
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-24 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1023166&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.

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