Computing Partition Functions in Hard Problems of Combinatorial Enumeration and Optimization

计算组合枚举和优化难题中的配分函数

• 批准号: 1361541
• 负责人: Alexander Barvinok
• 金额: $ 38万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1361541&HistoricalAwards=false
• 关键词: Computing; Partition; Functions; Hard; Problems

Problems of combinatorial optimization concern finding the optimal value of a function defined on a finite, though very large, set. Such problems have many real world applications and, for the most part, are notoriously difficult to solve, because the set of possible solutions is prohibitively large. The P.I. intends to investigate such problems through the approach of partition functions, the method inspired to a large extent by statistical physics. This will lead to new efficient algorithms in previously intractable problems.The particular problems addressed by the project include efficient computation of partition functions associated with perfect matching in (hyper)graphs, Hamiltonian cycles and cliques in graphs, graph homomorphisms, and systems of multivariate real quadratic equations. It will allow one to identify efficiently solvable cases of hard problems. For example, one will be able to efficiently distinguish graphs with sufficiently many (but still hard to find) Hamiltonian cycles from graphs that are sufficiently far away from Hamiltonian.

组合最优化的问题涉及找到一个函数的最优值定义在一个有限的，但非常大的，集。这类问题在真实的世界中有许多应用，而且在大多数情况下，由于可能的解决方案的集合太大，因此难以解决。私家侦探打算通过配分函数的方法来研究这些问题，该方法在很大程度上受到统计物理学的启发。这将导致新的高效算法在以前棘手的problems.The特定的问题，该项目所解决的包括有效的计算分区功能与完美匹配（超）图，哈密尔顿圈和图中的团，图同态，和系统的多变量真实的二次方程。它将使人们能够有效地识别困难问题的可解情况。例如，人们将能够有效地区分具有足够多（但仍然很难找到）的哈密尔顿圈的图与足够远离哈密尔顿圈的图。