  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.
