Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ON LINE ALGORITHMS:
Reports tagged with on line algorithms:
TR05-001 | 1st January 2005
Mario Szegedy

Near optimality of the priority sampling procedure

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 ... more >>>




ISSN 1433-8092 | Imprint