A Proposal for Research on Random Processes and Algorithms

随机过程和算法研究的提案

• 批准号: 9505448
• 负责人: Alistair Sinclair
• 金额: $ 31.52万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9505448&HistoricalAwards=false
• 关键词: Proposal; Research; Random; Processes; Algorithms

During the past decade, the quantitative analysis of random processes has led to dramatic advances in the design of efficient algorithms for fundamental computation problems. The PI is continuing research on the application of these ideas, as well as beginning to investigate new paradigms based on nonlinear and cooperative processes. Specifically, the project focuses on the following directions: (1) the analysis of mixing rates of Markov chains, with applications to efficient algorithms for problems in statistical physics and combinatorics; (2) the study of computational complexity of counting problems, and their classification with respect to efficient approximability; Algorithmic applications of nonlinear random processes, in particular quadratic dynamical systems; (3) the theoretical and experimental study of general randomized search heuristics in combinatorial optimization, including Metropolis algorithm, simulated annealing, and cooperative processes.

在过去的十年中，对随机过程的定量分析导致了基本计算问题的有效算法设计的显着进步。 PI正在继续研究这些思想的应用，并开始根据非线性和合作过程研究新的范式。 具体而言，该项目的重点是以下方向：（1）对马尔可夫链的混合速率进行分析，并应用于有效的统计物理和组合问题问题的有效算法； （2）研究计数问题的计算复杂性及其在有效近似性方面的分类； 非线性随机过程的算法应用，特别是二次动力学系统； （3）在组合优化中的一般随机搜索启发式方法的理论和实验研究，包括大都会算法，模拟退火和合作过程。