A Proposal for Research on Markov Chains, Approximate Counting and Finite Metric Spaces

关于马尔可夫链、近似计数和有限度量空间的研究建议

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

A Proposal for Research on Markov Chains, Approximate Counting and Finite Metric Spaces Alistair Sinclair University of California, BerkeleyThis project contains three loosely related themes: computational applications of Markov chains, approximate counting, and algorithmic apects of finite metric spaces.During the past decade, the so-called "Markov chain Monte Carlo method" has emerged as a powerful algorithmic paradigm, with applications in such areas as approximate counting, statistical physics and combinatorial optimization. The PI is pushing ahead with these applications, in the following three directions:Development of new techniques based on multicommodity flow to analyze geometric Markov chains (where the state space is the set of integer points inside a convex body).Investigation of techniques such as Chebyshev acceleration, which can potentially modify a Markov chain so as to substantially speed up its convergence.Improved understanding of newly emerging connections between the rapid mixing property of certain Markov chains on the configurations of physical systems and the thermodynamic properties of those systems.In parallel with recent activity aimed at classifying NP-hard optimization problems according to their degree of approximability, the PI is contributing to a similar classification of #P-hard counting problems. Specific aims here include:Investigation of novel algorithms for the central problem of approximating the permanent. Development of approximation-preserving reductions between counting problems so that, for example, a class of problems that are equivalent to the permanent can be constructed.Finite metric spaces provide a clean and elegant paradigm that captures (and often streamlines) several previously ad hoc algorithmic ideas. The third part of the project involves a systematic study of finite metrics, and specifically:The design of new techniques for l1 embedding, both in the general case (to achieve a distortion within o(log n) of optimal) and for special metrics (such as those supported on planar graphs). This has algorithmic applications to, among others, the central problem of approximating the sparsest cut in a network.Development of improved techniques for embeddings into low-dimensional spaces. These have applications to algorithms for ubiquitous problems such as nearest-neighbor searching and clustering.Approximation of complex metrics by simpler ones. This would allow existing algorithms that work well for simple metrics (such as trees) to be applied more widely.

关于马氏链、近似计数和有限度量空间研究的一个建议 阿利斯泰尔·辛克莱 加州大学伯克利分校该项目包含三个松散相关的主题：马尔可夫链的计算应用，近似计数和有限度量空间的算法方面。在过去的十年中，所谓的“马尔可夫链蒙特卡罗方法”已经成为一个强大的算法范例，在近似计数，统计物理和组合优化等领域的应用。 PI正在以下三个方向推进这些应用程序：基于多商品流的几何马尔可夫链分析新技术的发展（其中状态空间是凸体内部的整数点的集合）。对切比雪夫加速等技术的研究，它可以潜在地修改马尔可夫链，从而大大加快其收敛速度。提高了对物理系统配置上某些马尔可夫链的快速混合性质与这些系统的热力学性质之间新出现的联系的理解。与最近旨在分类NP-1的活动平行，硬优化问题，根据他们的近似程度，PI有助于类似的分类#P-硬计数问题。 这里的具体目标包括：调查的新算法的中心问题的近似永久。发展计数问题之间的近似保持约简，例如，可以构造一类等价于积式的问题。有限度量空间提供了一个干净优雅的范式，它捕获（并经常简化）了几个以前的特别算法思想。 该项目的第三部分涉及有限度量的系统研究，具体而言：设计l1嵌入的新技术，无论是在一般情况下（以实现最优的o（log n）内的失真）还是特殊度量（如平面图上支持的度量）。 这有算法应用，除其他外，在网络中近似稀疏割的中心问题。开发嵌入到低维空间的改进技术。这些应用程序的算法普遍存在的问题，如最近的邻居搜索和聚类。 这将使现有的算法，工作简单的指标（如树）更广泛地应用。