Stochastic enumeration method for counting NP-hard problems

DOI10.1007/S11009-011-9242-YMaRDI QIDQ352890zbMATH OpenOpenAlexFDO

Authors 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

numerical examplesMarkov chain Monte Carlo methodsatisfiabilitysplittingone-step-look-ahead algorithmpolynomial time decision makingrare-eventsample search methodsself-avoiding walkssequential importance sampling algorithmstochastic enumeration

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Combinatorial probability (60C05)

Recommendations

• Stochastic enumeration method for counting trees
• Stochastic enumeration with importance sampling
• How many needles are in a haystack, or how to solve \#P-complete counting problems fast
• Monte-Carlo approximation algorithms for enumeration problems
• An analysis of Monte Carlo algorithms for counting problems

Cites work

• scientific article; zbMATH DE number 2106098 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A Two-Step Branching Splitting Model Under Cost Constraint for Rare Event Analysis
• A machine program for theorem-proving
• Adaptive Multilevel Splitting for Rare Event Analysis
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• Approximating the permanent: A simple approach
• Efficient Monte Carlo simulation via the generalized splitting method
• Efficient implementation of the Pivot algorithm for self-avoiding walks
• Equation of state calculations by fast computing machines
• Estimating the Number of s-t Paths in a Graph
• Genetic genealogical models in rare event analysis
• Monte Carlo methods for the self-avoiding walk
• Monte Carlo strategies in scientific computing
• Multilevel splitting for estimating rare event probabilities
• Probability and Computing
• RARE EVENT SIMULATION
• Random generation of combinatorial structures from a uniform distribution
• SampleSearch: importance sampling in presence of determinism
• Sequential Monte Carlo for rare event estimation
• Simulation and the Monte Carlo Method
• The Gibbs cloner for combinatorial optimization, counting and sampling
• The complexity of computing the permanent
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• Theory and Applications of Satisfiability Testing

Cited in

(8)

• Model counting of monotone conjunctive normal form formulas with spectra
• Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work
• Approximate verification and enumeration problems
• Monte-Carlo approximation algorithms for enumeration problems
• How many needles are in a haystack, or how to solve \#P-complete counting problems fast
• Stochastic enumeration method for counting trees
• Stochastic enumeration with importance sampling
• Sequential Monte Carlo for counting vertex covers in general graphs

This page was built for publication: Stochastic enumeration method for counting NP-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352890)