|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
University of Michigan Title: Computing partition functions in hard problems of combinatorial optimization Abstract: Consider an NP-complete problem, such as finding whether a given graph G on n vertices contains a Hamiltonian cycle. First, we attempt to solve an even more general problem: given an n × n non-negative matrix A, interpreted as the matrix of weights on the edges of the complete graph Kn, we consider the sum (partition function) over all Hamiltonian cycles in Kn of the products of weights on the edges of the cycle. Thus if A the adjacency matrix of G, we obtain the number of Hamiltonian cycles in G. Next, we modify A by replacing all zeros with some positive epsilons. It turns out that the partition function becomes efficiently computable, which allows us to distinguish graphs that are far from having a Hamiltonian cycles from graphs that have many Hamiltonian cycles (even when "many" still means that the probability to hit a Hamiltonian cycle at random is exponentially small). In a joint work with P. Soberon, we attempt to establish the most general framework when this approach appears to work: it concerns computing the partition function of graph homomorphisms with multiplicities, which allows us to handle Hamiltonian cycles, independent sets, dense subgraphs and colorings. |
