Computing Partition Functions in Hard Problems of Combinatorial Enumeration and Optimization

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.