Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-001 | 1st January 2005 00:00

Near optimality of the priority sampling procedure

RSS-Feed




TR05-001
Authors: Mario Szegedy
Publication: 3rd January 2005 10:44
Downloads: 3497
Keywords: 


Abstract:

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal among all
{\em off-line} sampling procedures.
Here we prove this conjecture. In particular, our result gives an affirmative answer to the conjecture of
N. Alon, N. Duffield, C. Lund and M. Thorup \cite{adlt}, which states that the standard deviation for
the subset sum estimator obtained from $k$ priority samples is upper bounded by $W/\sqrt{k-1}$.
($W$ is the actual subset sum.)



ISSN 1433-8092 | Imprint