Search cost for a nearly optimal path in a binary tree

Details Search cost for a nearly optimal path in a binary tree Search cost for a nearly optimal path in a binary tree

2007-01-25

arxiv.org/abs/math/0701741v2

Annals of Applied Probability 2009, Vol. 19, No. 4, 1273-1291

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/08-AAP585 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/08-AAP585

Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean $p\leq1/2$. How many of these Bernoullis one must look at in order to find a path of length $n$ from the root which maximizes, up to a factor of $1-\epsilon$, the sum of the Bernoullis along the path? In the case $p=1/2$ (the critical value for nontriviality), it is shown to take $\Theta(\epsilon^{-1}n)$ steps. In the case $p<1/2$, the number of steps is shown to be at least $n\cdot\exp(\operatorname {const}\epsilon^{-1/2})$. This last result matches the known upper bound from [Algorithmica 22 (1998) 388--412] in a certain family of subcases.

Affiliated with

Also associated with

No associations

Rating

Search cost for a nearly optimal path in a binary tree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Search cost for a nearly optimal path in a binary tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search cost for a nearly optimal path in a binary tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-329176