Random Trees and the Analysis of Branch and Bound Procedures

Branch and bound procedures are the most efficient known means for solving many NP-hard problems A special class of branch and bound procedures called relaxation-gutded procedures ig presented. While for some branch and bound procedures a worst-case complexity bound is known, the average case complexity is usually unknown, despite the fact that it may g~ve more useful information about the performance of the algorithm. A random process which generates labeled trees is introduced as a model of the kind of trees that a relaxatlon-gutded procedure generates over random instances of a problem Results concerning the expected time and space complexity of searching these random trees are derived with respect to several search strategies. The best-bound search strategy is shown to be optimal in both time and space. These results are illustrated by data from random traveling salesman instances Evidence ~s presented that the asymmetric traveling salesman problem can be solved exactly in time O(n31n(n)) on the average.