Stochastic Enumeration Method for Counting NP-Hard Problems |
| |
Authors: | Reuven Rubinstein |
| |
Institution: | 1. Faculty of Industrial Engineering and Technion, Israel Institute of Technology, Haifa, Israel
|
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|