Stochastic enumeration method for counting NP-hard problems

DOI10.1007/s11009-011-9242-yzbMath1269.65012MaRDI QIDQ352890

Reuven Y. Rubinstein

Publication date: 5 July 2013

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11009-011-9242-y

zbMATH Keywords

Markov chain Monte Carlo method; numerical examples; self-avoiding walks; splitting; satisfiability; one-step-look-ahead algorithm; polynomial time decision making; rare-event; sample search methods; sequential importance sampling algorithm; stochastic enumeration

Mathematics Subject Classification ID

60J22: Computational methods in Markov chains

65C05: Monte Carlo methods

60C05: Combinatorial probability

65C40: Numerical analysis or methods applied to Markov chains

Related Items

Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• SampleSearch: importance sampling in presence of determinism
• The complexity of computing the permanent
• Sequential Monte Carlo for rare event estimation
• Efficient Monte Carlo simulation via the generalized splitting method
• The Gibbs cloner for combinatorial optimization, counting and sampling
• Random generation of combinatorial structures from a uniform distribution
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• Multilevel Splitting for Estimating Rare Event Probabilities
• Adaptive Multilevel Splitting for Rare Event Analysis
• Monte Carlo methods for the self-avoiding walk
• Approximating the permanent: A simple approach
• Equation of State Calculations by Fast Computing Machines
• RARE EVENT SIMULATION
• Estimating the Number of s-t Paths in a Graph
• A Two-Step Branching Splitting Model Under Cost Constraint for Rare Event Analysis
• Simulation and the Monte Carlo Method
• Probability and Computing
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Monte Carlo strategies in scientific computing
• Efficient implementation of the Pivot algorithm for self-avoiding walks