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.

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