Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work

DOI10.1007/s11009-009-9126-6zbMath1187.65001MaRDI QIDQ2270192

Reuven Y. Rubinstein

Publication date: 15 March 2010

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

Full work available at URL: https://doi.org/10.1007/s11009-009-9126-6

zbMATH Keywords

algorithms; Markov chains; importance sampling; Markov chain Monte Carlo method; numerical examples; rare events; combinatorial optimization; Gibbs sampler; randomized algorithms; approximate counting; cloning algorithm

Mathematics Subject Classification ID

60J22: Computational methods in Markov chains

65C05: Monte Carlo methods

90C27: Combinatorial optimization

60C05: Combinatorial probability

65C40: Numerical analysis or methods applied to Markov chains

68W20: Randomized algorithms

Related Items

The Splitting Method for Decision Making, Concentration inequalities for mean field particle models, Sequential importance sampling of binary sequences, Rare event simulation and splitting for discontinuous random variables, On the Use of Smoothing to Improve the Performance of the Splitting Method, Counting with Combined Splitting and Capture–Recapture Methods, HOW TO GENERATE UNIFORM SAMPLES ON DISCRETE SETS USING THE SPLITTING METHOD

Cites Work

• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• The Gibbs cloner for combinatorial optimization, counting and sampling
• Discrete Hit-and-Run for Sampling Points from Arbitrary Distributions Over Subsets of Integer Hyperrectangles
• Randomly coloring planar graphs with fewer colors than the maximum degree
• Probability and Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item