A common schema for dynamic programming and branch and bound algorithms

A common schema for dynamic programming and branch and bound algorithms

0.00 Avg rating0 Votes
Article ID: iaor19881125
Country: United States
Volume: 36
Issue: 1
Start Page Number: 97
End Page Number: 128
Publication Date: Jan 1989
Journal: Journal of the Association for Computing Machinery
Authors:
Keywords: programming: dynamic, programming: branch and bound
Abstract:

A new model for dynamic programming and branch and bound algorithms is presented. The model views these algorithms as utilizing computationally feasible dominance relations to infer the orderings of application objects, thereby implicitly enumerating a finite solution space. The formalism is broad enough to apply the computational strategies of dynamic programming and branch and bound to problems with nonassociative objects, and can model both oblivious and nonoblivious algorithms, as well as parallel algorithms. The model is used to classify computations based, in part, on the types of computationally feasible dominances that they employ. It is demonstrated that the model is computationally precise enough to support the derivation of lower bounds on the number of operations required to solve various types of problems.

Reviews

Required fields are marked *. Your email address will not be published.