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

Reuven Y. Rubinstein ()
Additional contact information
Reuven Y. Rubinstein: Faculty of Industrial Engineering and Management, Technion

Methodology and Computing in Applied Probability, 2006, vol. 8, issue 1, 5-51

Abstract: Abstract We present two randomized entropy-based algorithms for approximating quite general #P-complete counting problems, like the number of Hamiltonian cycles in a graph, the permanent, the number of self-avoiding walks and the satisfiability problem. In our algorithms we first cast the underlying counting problem into an associate rare-event probability estimation, and then apply dynamic importance sampling (IS) to estimate efficiently the desired counting quantity. We construct the IS distribution by using two different approaches: one based on the cross-entropy (CE) method and the other one on the stochastic version of the well known minimum entropy (MinxEnt) method. We also establish convergence of our algorithms and confidence intervals for some special settings and present supportive numerical results, which strongly suggest that both ones (CE and MinxEnt) have polynomial running time in the size of the problem.

Keywords: Cross-entropy; Rare-event probability estimation; Hamilton cycles; Self-avoiding walks; #P-complete problems; Stochastic and simulation-based optimization (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-006-7287-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:8:y:2006:i:1:d:10.1007_s11009-006-7287-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-006-7287-0

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().