✦ LIBER ✦

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

✍ Scribed by Luc Devroye; Carlos Zamora-Cura

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 256 KB
Volume: 14
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199907)14:4<309::aid-rsa2>3.0.co;2-1

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be a b-ary tree of height n, which has independent, non-negative, n 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 Ä 4 value of T . Assume that the edge random variable X is nondegenerate, has E X -ϱ for n Ä 4 some ) 2, and satisfies bP X s 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 Ž Ž .. n Ž . and prove that the number of nodes visited is in probability ␤ q o 1 , where ␤ g 1, b is a constant depending only on the distribution of the edge random variables. Explicit expres-Ž Ž .. n sions for ␤ are derived. We also show that any search algorithm must visit ␤ q o 1 nodes with probability tending to 1, so branch-and-bound is asymptotically optimal where first-order asymptotics are concerned.

📜 SIMILAR VOLUMES

The critical-item, upper bounds, and a b

The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem

✍ Shaw, Dong X.; Cho, Geon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB 👁 1 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac

Upper and lower bounds for the average-c

Upper and lower bounds for the average-case complexity of path-search

✍ Pippenger, Nicholas 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent

On the profile of random trees

✍ Michael Drmota; Bernhard Gittenberger 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe

Upper bounds on the height difference of

Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into ℤ

✍ Itai Benjamini; Gideon Schechtman 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 1 views

On the log-product of the subtree-sizes

On the log-product of the subtree-sizes of random trees

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

We determine the asymptotic behavior of the expected value and the variance of the log-product of the subtree-sizes of trees T belonging to simply generated families of n

A fast algorithm for a k-NN classifier b

A fast algorithm for a k-NN classifier based on the branch and bound method and computational quantity estimation

✍ Shin'ichiro Omachi; Hirotomo Aso 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 1 views

The nearest neighbor rule or k-nearest neighbor rule is a technique of nonparametric pattern recognition. Its algorithm is simple and the error is smaller than twice the Bayes error if there are enough training samples. However, it requires an enormous amount of computation, proportional to the numb