Technical Note—On the Expected Performance of Branch-and-Bound Algorithms

For many combinatorial optimization problems, the use of enumerative solution methods exhibiting a superpolynomial worst-case behavior seems unavoidable. It is therefore of interest to investigate the expected behavior of such methods. Polynomial-bounded expected performance has been claimed by Bellmore and Malone for their traveling salesman algorithm. The purpose of this brief note is to point out some inadequacies of their proof.