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.

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