"Bucket Elimination: A Unifying Framework for automated reasoning"

4/17/1998: [time not recorded]
[location not recorded]

Abstract: Bucket elimination, is an algorithmic framework that unifies many complex problem-solving and reasoning tasks. Algorithms such as directional-resolution for propositional satisfiability, adaptive-consistency for constraint satisfaction, Fourier and Gaussian elimination, for solving linear equalities and inequalities and dynamic programming for combinatorial optimization, as well as probabilistic inference such as, belief updating, finding the most probable explanation and the maximum expected utility, can all be accommodated within the bucket elimination framework. The generality of this framework encourages the transfer of heuristics and techniques across disciplines. The algorithms mentioned above share the same performance guarantees; all are time and space exponential in the tree-width embedding of the problem's interaction graph. In this talk I will demonstrate the applicability of the framework, and will contrast bucket elimination with conditioning, another known universal method for problem solving that is time exponential, but does not suffer from the space complexity of elimination. I will then present a uniform way of combining conditioning with elimination that can be used to trade space for time and time for accuracy. Finally, I will present the mini-bucket scheme; a new approach for approximating bucket elimination which offers an adjustable level of accuracy and efficiency. Applications to medical diagnosis and decoding algorithms will be given.

Last updated: Mon Jun 19 17:44:06 2006