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)组合优化中通用随机搜索启发式的理论和实验研究，包括Metropolis算法、模拟退火和协作过程。