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）组合优化中一般随机搜索算法的理论和实验研究，包括大都会算法、模拟退火算法、和合作进程。