Login
Computer Science @ Rochester
Monday, April 27, 2009
9:00 AM
Computer Studies Bldg. Room 703
Ph.D. Thesis Proposal
Qi Ge
University of Rochester
Approximate Counting by Markov Chain Monte Carlo Method
Markov chain Monte Carlo method is a standard method for sampling. From the algorithmic point of view, two problems arise that how to construct a Markov chain for the problem and how many steps are needed before the distribution is close enough to the desired distribution. They are the core problems in designing Markov chains for approximate counting.

In this paper, we propose two directions which we will investigate in the future work. One is the simulated annealing method and the other is the multi-decomposition method.

Simulated annealing method is useful especially in designing efficient approximate algorithms for the problems of computing weighted combinatorial structures. Since the mixing time of the Markov chain for this kind of problems can depend on the value of the weights instead of the size of the values in binary, e.g. weighted matchings in bipartite graphs. We present some results we have for counting weighted matchings in bipartite graphs and related problems, e.g. the ice-model. We also present our experiment for solving the problem of counting weighted matchings in general graphs.

Destainville proposed the method of multi-decomposition. The advantage of multi-decomposition is that it allows us to apply the multi-decomposition recursively if the structure of the state space is in some sense symmetric. We are exploring applications of the multi-decomposition method on two problems, one is counting the number Eulerian tours in 4-regular graphs and the other is counting the forests in given graphs. Some partial results and conjectures are given.