How Many Needles are in a Hay Stack,
or How to Solve #P-Complete Counting Problems Fast
Reuven Rubinstein
Faculty of Industrial and Engineering Management
Technion
Tuesday, February 28, 2006
4:30 - 5:45 PM
Terman Engineering Center, Room 453
Abstract:
We present a new generic randomized algorithm for approximating quite
general #P-complete counting problems, like the number of Hamiltonian
cycles in a graph, the permanent, and the number of self-avoiding
walks of certain length. To do so we cast the underlying counting
problem into an associate rare-event probability estimation one, and
then apply the cross-entropy (CE) method for updating the parameters
of the importance sampling (IS) distribution. We use importance
sampling to speed up the simulation process and, thus to produce a low
variance estimate of the desired counting quantity.
We establish convergence and speed of convergence of our algorithm for
some particular #P-complete counting problems and present supportive
numerical results, which strongly suggest that the presented algorithm
has polynomial complexity in the size of the network.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html