On the complexity of branch-and-bound search for random trees

Let T-n be a b-ary tree of height n, which has independent, non-negative, i dentically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The va lue of a node is the sum of all the edge values on its path to the root. Co nsider the problem of finding the minimum leaf value of T-n. Assume that th e edge random variable X is nondegenerate, has E{X-theta} < infinity for so me theta > 2, and satisfies bP{X = c} < 1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch-and-bou nd algorithm for this problem and prove that the number of nodes visited is in probability (beta + o(1))(n), where beta is an element of(1, b) is a co nstant depending only on the distribution of the edge random variables. Exp licit expressions for beta are derived. We also show that any search algori thm must visit (beta + o(1))(n) nodes with probability tending to 1, so bra nch-and-bound is asymptotically optimal where first-order asymptotics are c oncerned. (C) 1999 John Wiley & Sons, Inc.