Back to Search
Start Over
Stochastic Enumeration Method for Counting NP-Hard Problems.
- Source :
- Methodology & Computing in Applied Probability; Jun2013, Vol. 15 Issue 2, p249-291, 43p, 19 Diagrams, 14 Charts, 1 Graph
- Publication Year :
- 2013
-
Abstract
- We present a new generic sequential importance sampling algorithm, called stochastic enumeration (SE) for counting #P-complete problems, such as the number of satisfiability assignments and the number of perfect matchings (permanent). We show that SE presents a natural generalization of the classic one-step-look-ahead algorithm in the sense that it: Runs in parallel multiple trajectories instead of a single one; Employs a polynomial time decision making oracle, which can be viewed as an n-step-look-ahead algorithm, where n is the size of the problem. Our simulation studies indicate good performance of SE as compared with the well-known splitting and SampleSearch methods. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13875841
- Volume :
- 15
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Methodology & Computing in Applied Probability
- Publication Type :
- Academic Journal
- Accession number :
- 87090823
- Full Text :
- https://doi.org/10.1007/s11009-011-9242-y