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-难问题之一。平均情况的复杂度在一段时间前被降低到多项式时间，该项目的目标之一是将其降低到尽可能接近预期的线性时间。 该项目还将涉及平均情况复杂性的其他几个问题。所采用的方法将涉及随机图领域的工具和技术。两个主要的工具是集中的措施和集中的事件发生的概率接近一。该项目还将考虑使用快速混合马尔可夫链生成随机着色的图形和超图。该主题与统计物理学有着密切的联系，并从思想的交叉中受益匪浅。尽管图论至少有100年的历史，但直到最近几年，图或网络的普遍性才被广泛认识到。随机图的研究大约有50年的历史，需要从这一领域的技术来研究真实的世界网络。仅仅因为它们以一种看似随机的方式进化。该项目将涉及这一领域的若干分析。 例如，我们不知道随机图的组成结构是什么，它在优先连接下进化，但会被删除。