Computing Partition Functions in Hard Problems of Combinatorial Enumeration and Optimization

组合优化问题涉及寻找定义在有限但非常大的集合上的函数的最佳值。这类问题有许多现实应用，而且在很大程度上是出了名的难以解决，因为可能的解决方案集大得令人望而却步。P.I.打算通过配分函数的方法来研究这些问题，这种方法在很大程度上受到统计物理学的启发。这将导致新的有效的算法来解决以前难以解决的问题。该项目所解决的特殊问题包括(超)图中与完美匹配相关的配分函数的有效计算、图中的哈密顿圈和团、图的同态以及多元实二次方程组。它将使人们能够有效地识别困难问题的可解决案例。例如，人们将能够有效地区分具有足够多(但仍然很难找到)哈密顿圈的图和距离哈密顿足够远的图。

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.