Local Algorithms for Random Networks: Power, Limitations and Applications

随机网络的局部算法：能力、限制和应用

• 批准号: 1335155
• 负责人: David Gamarnik
• 金额: $ 36万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1335155&HistoricalAwards=false
• 关键词: Local; Algorithms; Random; Networks; Power

The research objective of this award is to develop systematic understanding of the performance and limitations of local algorithms for combinatorial optimization problems on random networks. The scale of modern technological, communication and social networks renders many computational tools and concepts too impractical to meet the contemporary computational speeds. In light of this challenge, the research on network computational models has recently focused on local algorithms paradigm. One of the most common generative models for real life networks is the random graph model. Thus the research focuses on the performance and limitations of local algorithms for random graphs. A particular focus is on studying the so-called solution space geometry of combinatorial problems on random graphs and its implications for the design and analysis of local algorithms. It is now known that certain optimization problems undergo a phase transition property, dubbed shattering, described as splitting of the space of feasible solutions into many disconnected components. Many attempts to construct algorithms which perform beyond this phase transition point did not succeed. Thus the shattering property is conjectured to be the main "culprit" for the non-existence of local algorithms beyond the phase transition point. A recent work of the PI establishes the non-existence of local algorithms for some optimization problems beyond this phase transition point, thus establishing for the first time the direct link between the shattering phase transition property and the performance of algorithms. The research focuses on the systematic study of this fascinating link between the phase transition property and the design of algorithms. If successful, the results of this research will provide a deep connection between the performance and algorithmic complexity of local algorithms and structural properties of random networks. The research agenda is truly interdisciplinary, lying at the crossroads of several fields. The activities draw on tools from a variety of disciplines, including the theory of algorithms, combinatorics and graph theory, applied probability and statistical physics, thus bringing together ideas from a diverse set of communities. The results of this research will be disseminated in top journals and conferences in the respective fields. Research seminars will be conducted to introduce students to the topic of algorithms and computations on networks.

该奖项的研究目标是对随机网络上组合优化问题的局部算法的性能和局限性进行系统的理解。现代技术、通信和社会网络的规模使得许多计算工具和概念过于不切实际，无法满足当代的计算速度。鉴于这一挑战，网络计算模型的研究最近主要集中在局部算法范式上。现实生活网络中最常见的生成模型之一是随机图模型。因此，研究的重点是随机图局部算法的性能和局限性。特别的重点是研究所谓的随机图组合问题的解空间几何及其对局部算法的设计和分析的影响。现在我们知道，某些优化问题经历了一种称为破碎的相变特性，即可行解的空间分裂成许多不相连的组件。许多尝试构建超越这一相变点的算法都没有成功。因此，我们推测，在相变点之外不存在局部算法的主要“罪魁祸首”是破碎性。PI最近的一项工作建立了局部算法在该相位点以外的一些优化问题的不存在性，从而首次建立了破碎相变特性与算法性能之间的直接联系。研究的重点是系统地研究相变特性与算法设计之间的这种迷人联系。如果成功，本研究的结果将为局部算法的性能和算法复杂性以及随机网络的结构特性之间提供深入的联系。研究议程是真正的跨学科，位于几个领域的十字路口。这些活动利用了各种学科的工具，包括算法理论、组合学和图论、应用概率论和统计物理学，从而汇集了来自不同社区的想法。这项研究的结果将在各自领域的顶级期刊和会议上发表。将举办研究研讨会，向学生介绍网络上的算法和计算。