Probabilistic Considerations in the Analysis of Algorithms

算法分析中的概率考虑

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

The investigator will continue his work on the interplay betweenprobability and algorithms. He has identified two distinct but very important aspects of such study. In the first instance he will study randomized algorithms i.e. those algorithms that introduce randomnessas a means of speeding up computation. In the second instance, he will consider the average case performance of algorithms. Here, he wants to tryto explain the good performance of simple algorithms on "typical" problems as opposed to the worst-case performance exemplified by the pathological examples of complexity theory.In the area of randomized algorithms, the investigator will considerproblems arising in the study of Monte Carlo Markov Chain algorithms.In particular he will study their use in problems associated with combinatorial counting problems and with problems in Statistical Physics. He will also continue his study of the Edge Disjoint Path problem and the construction of a generalisation of the well knownmatrix Singular Value Decomposition to multi-dimensional matrices. In the area of average case analysis, he will continue his work on theTraveling Salesman Problem and try to extend his ideas to the independent symmetric model. He will continue his work on analysing the efficacy of the Sequencing By Hybridization technique in ComputationalBiology. Finally, he will continue to work on probabilistic models of theWorld Wide Web in an attempt to find a useful model for the testing of algorithmic ideas.

研究人员将继续研究概率和算法之间的相互作用。他确定了此类研究的两个不同但非常重要的方面。首先，他将研究随机算法，即引入随机性作为加速计算的手段的算法。在第二种情况下，他将考虑算法的平均情况性能。在这里，他想尝试解释简单算法在“典型”问题上的良好性能，而不是复杂性理论的病态例子所例证的最坏情况性能。在随机算法领域，研究者将考虑研究中出现的问题他将研究它们在与组合计数问题和统计物理问题相关的问题中的应用。他还将继续研究边不相交路径问题以及将众所周知的矩阵奇异值分解推广到多维矩阵的构造。在平均案例分析领域，他将继续他对旅行商问题的研究，并尝试将他的想法扩展到独立对称模型。他将继续分析计算生物学中杂交测序技术的功效。最后，他将继续研究万维网的概率模型，试图找到一个有用的模型来测试算法思想。