School Seminars and Colloquia

How Many Needles are in a Haystack or how to Solve #P-Complete Counting Problems Fast

MASCOS/COSNET seminar

by Reuven Rubinstein


Institution: Faculty of Industrial Engineering and Management, Technion
Date: Fri 8th September 2006
Time: 3:15 PM
Location: Theatre 1, Ground Floor, 111 Barry Street, Carlton

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.
For more details see our homepage www.cemethod.org and for wikipedia - the cross-entropy method.

For More Information: Emma Lockwood emmal@ms.unimelb.edu.au Tel: +61 3 8344 1617