AF: Small: Probabilistic Considerations in the Analysis of Algorithms

AF：小：算法分析中的概率考虑

• 批准号: 1013110
• 负责人: ALAN FRIEZE
• 金额: $ 46.62万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1013110&HistoricalAwards=false
• 关键词: AF; Small; Probabilistic; Considerations; Analysis

The aim of this project is to advance the understanding of various aspects of probability in relation to algorithm design and analysis. In general this means the study of randomized algorithms, the average case performance of algorithms and related, seemingly random, structures such as social networks. Randomized algorithms are important because they are often the most efficient and some times the only efficient way to solve computational problems. The study of the average case sheds light on why problems which in the worst-case seem computationally difficult or even intractable, can be routinely solved in practise, by simple algorithms. The research on random models of large real world networks is important for answering algorithmic questions about them and for understanding their evolution.The project will study several important problems from the point of view of average case analysis: (i) Cuckoo Hashing is a relatively new hashing algorithm and some of the basic questions about its performance remain unanswered, even though there has been significant progress of late. (ii) The matching problem for graphs is the quintissential polynomial time solvable problem in Combinatorial Optimiztion. Its polynomial time solution is one of the great achievements of the area. Its worst-case complexity, while polynomial still leaves room for improvement and one of the aims of the project is to settle the average case completely. (iii) The hamilton cycle problem for graphs is one of the canonical NP-hard problems. The average-case complexity was reduced to polynomial time some time ago and one of the aims of the project is to reduce this to as close to expected linear time as possible. The project will also several other problems involving average case complexity. The methodology employed will involve the tools and techniques from the field of Random Graphs. The two main tools being concentration of measure and concentration on events that happen with probability close to one.The project will also consider the use of Rapidly Mixing Markov Chains to generate random colorings of graphs and hypergraphs. This topic has close ties to Statistical Physics and has benefited a great deal from the cross-fertilization of ideas. There are still many gaps, particularly in the case of hypergraphs, and the project aims to close them.While graph theory is at least a hundred years old, it is only in recent years that the ubiquitousness of graphs or networks has been so widely recognized. The study of Random Graphs is about fifty years old and techniques from this area are needed to study real world networks. Simply because they evolve in a seemingly random manner. The project will involve several analyses from this area. For example, it is not known what is the component structure of a random graph, evolving under preferential attachment but subject to deletions.

该项目的目的是增进对与算法设计和分析相关的概率各个方面的理解。一般来说，这意味着研究随机算法、算法的平均情况性能以及相关的、看似随机的结构，例如社交网络。随机算法很重要，因为它们通常是解决计算问题最有效的方法，有时甚至是唯一有效的方法。对平均情况的研究揭示了为什么在最坏情况下看起来计算困难甚至棘手的问题可以在实践中通过简单的算法常规解决。对大型现实世界网络的随机模型的研究对于回答有关它们的算法问题和理解它们的演化具有重要意义。该项目将从平均案例分析的角度研究几个重要问题：（i）布谷鸟哈希是一个相对较新的算法。尽管最近取得了重大进展，但哈希算法及其性能的一些基本问题仍未得到解答。 (ii) 图的匹配问题是组合优化中典型的多项式时间可解问题。其多项式时间解是该领域的伟大成就之一。其最坏情况的复杂性，而多项式仍有改进的空间，该项目的目标之一是完全解决平均情况。 (iii) 图的哈密尔顿循环问题是典型的 NP 难问题之一。平均情况的复杂性不久前已降低至多项式时间，该项目的目标之一是将其降低至尽可能接近预期的线性时间。 该项目还将解决涉及平均情况复杂性的其他几个问题。所采用的方法将涉及随机图领域的工具和技术。两个主要工具是集中测量和集中发生概率接近 1 的事件。该项目还将考虑使用快速混合马尔可夫链来生成图和超图的随机着色。该主题与统计物理学密切相关，并从思想的交叉融合中受益匪浅。仍然存在许多差距，特别是在超图方面，该项目旨在弥合这些差距。虽然图论至少有一百年的历史，但直到最近几年，图或网络的普遍性才得到如此广泛的认可。随机图的研究已有大约五十年的历史，需要该领域的技术来研究现实世界的网络。仅仅是因为它们以看似随机的方式进化。该项目将涉及该领域的多项分析。 例如，不知道随机图的组件结构是什么，在优先附着下演化但可能会被删除。