Report Number: CS-TR-74-442
Institution: Stanford University, Department of Computer Science
Title: Estimating the efficiency of backtrack programs.
Author: Knuth, Donald E.
Date: August 1974
Abstract: One of the chief difficulties associated with the so-called
backtracking technique for combinatorial problems has been
our inability to predict the efficiency of a given algorithm,
or to compare the efficiencies of different approaches,
without actually writing and running the programs. This paper
presents a simple method which produces reasonable estimates
for most applications, requiring only a modest amount of hand
calculation. The method should prove to be of considerable
utility in connection with D. H. Lehmer's branch-and-bound
approach to combinatorial optimization.