Name
Abstract | ||
|---|---|---|
A typical approach to estimate an unknown quantity $\mu$ is to design an experiment that produces a random variable Z, distributed in [0,1] with E[Z]=\mu$, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1]. We describe an approximation algorithm ${\cal A}{\cal A}$ which, given $\epsilon$ and $\delta$, when running independent experiments with respect to any Z, produces an estimate that is within a factor $1+\epsilon$ of $\mu$ with probability at least $1-\delta$. We prove that the expected number of experiments run by ${\cal A}{\cal A}$ (which depends on Z) is optimal to within a constant factor {for every} Z. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1137/S0097539797315306 | SIAM J. Comput. |
Keywords | DocType | Volume |
constant factor,expected number,spl delta,monte carlo estimation,approximation algorithm,spl mu,typical approach,optimal algorithm,approximation algorithm aa,unknown quantity,spl epsiv,random variable z,independent experiment,probability,approximation algorithms,monte carlo,computer science,monte carlo methods,estimation theory,random variables,random variable,algorithm design and analysis,parallel algorithms,upper bound | Journal | 29 |
Issue | ISSN | ISBN |
5 | 0272-5428 | 0-8186-7183-1 |
Citations | PageRank | References |
106 | 8.84 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Dagum | 1 | 106 | 8.84 |
| R. M. Karp | 2 | 14427 | 3783.81 |
| Michael Luby | 3 | 9010 | 1319.35 |
| Sheldon M. Ross | 4 | 145 | 20.28 |