The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
An Optimal Algorithm for Monte Carlo Estimation
Paul Dagum, Richard Karp, Michael Luby, Sheldon Ross,
Pages. 1484-1496
Abstract
Contents 1. Introduction 2. Approximation algorithm 3. Lower bound 4. Preliminaries for the proofs 5. Proof of the Stopping Rule Theorem 6. Proof of the $\mathcal{AA}$ Theorem 7. Proof of the Lower Bound Theorem
Key words stopping rule, approximation algorithm, Monte Carlo estimation, sequential estimation, stochastic approximation
Mathmatical Subject Classification 60G40, 60G44