An Optimal Algorithm for Monte Carlo Estimation
From MaRDI portal
Publication:4943879
DOI10.1137/S0097539797315306zbMath1112.65300MaRDI QIDQ4943879
Paul Dagum, Michael Luby, Sheldon M. Ross, Richard M. Karp
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
stochastic approximationapproximation algorithmstopping rulesequential estimationMonte Carlo estimation
Related Items (25)
Fast approximate probabilistically checkable proofs ⋮ Approximate distributed top-\(k\) queries ⋮ Inverse Sampling for Nonasymptotic Sequential Estimation of Bounded Variable Means ⋮ Optimal aggregation algorithms for middleware. ⋮ Estimating global subgraph counts by sampling ⋮ Nearly Optimal Bernoulli Factories for Linear Functions ⋮ A Bernoulli mean estimate with known relative error distribution ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ A theory of truncated inverse sampling ⋮ Faster estimates of the mean of bounded random variables ⋮ Rumor correction maximization problem in social networks ⋮ Probabilistic verification and approximation ⋮ Solvable integration problems and optimal sample size selection ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Computational complexity of impact size estimation for spreading processes on networks ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ Viral marketing of online game by DS decomposition in social networks ⋮ High-confidence estimation of small s -t reliabilities in directed acyclic networks ⋮ Quantum Chebyshev's Inequality and Applications ⋮ The query complexity of estimating weighted averages ⋮ Unnamed Item ⋮ Fixed relative precision estimators of growth rate for compound Poisson and Lévy processes ⋮ Query answering over inconsistent knowledge bases: a probabilistic approach ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
This page was built for publication: An Optimal Algorithm for Monte Carlo Estimation
