On the computational complexity of branch and bound search strategies
By: by Douglas R. Smith
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1979
Place of publication: Monterey, Calif
Language: eng
Number of pages: 101
Subjects: Combinatorial optimization
Description: Many important problems in operations research, artificial intelligence, combinatorial algorithms, and other areas seem to require search in order to find an optimal solution.  A branch and bound procedure, which imposes a tree structure on the search, is often the most efficient known means for solving these problems.  While for some branch and bound algorithms a worst case complexity bound is known, the average case complexity is usually unknown despite the fact that it gives more information about the performance of the algorithm.  In this dissertation the branch and bound method is discussed and a proabilistic model of its domain is given, namely a class of trees with an associated probability measure.  The best bound first and depth-first search strategies are discusses and results on the expected time and space complexity of these strategies are presented and compared.  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 problems.  Evidence is presented which suggests that the asymmetric traveling salesman problem can be solved exactly in time O(n³ln²(n)) on the
Notes: Title from cover.

"Prepared for: National Science Foundation; Washington, D.C. 20550"--Cover.

"November 1979"--Cover.

"NPS-52-79-004"--Cover.

Includes bibliographical references (p. 96-100).

"Approved for public release; distribution unlimited"--Cover.

Technical report; 1979.