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, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T-n. Assume that the edge random variable X is nondegenerate, has E{X-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-bound 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 constant depending only on the distribution of the edge random variables. Explicit expressions for beta are derived. We also show that any search algorithm must visit (beta + o(1))(n) nodes with probability tending to 1, so branch-and-bound is asymptotically optimal where first-order asymptotics are concerned. (C) 1999 John Wiley & Sons, Inc.
branch-and-bound search algorithms probabilistic analysis tree search expected complexity lower bounds