Stochastic Enumeration Method for Counting NP-Hard Problems

Reuven Rubinstein ()
Additional contact information
Reuven Rubinstein: Israel Institute of Technology

Methodology and Computing in Applied Probability, 2013, vol. 15, issue 2, 249-291

Abstract: 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.

Keywords: Counting; MCMC; Rare-event; Self-avoiding walks; Satisfiability; Sequential importance sampling; Splitting; 65C05; 60C05; 68W20; 90C59 (search for similar items in EconPapers)
Date: 2013
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-011-9242-y 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:15:y:2013:i:2:d:10.1007_s11009-011-9242-y

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

DOI: 10.1007/s11009-011-9242-y

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 ().