Abstract
Bucket elimination is an algorithmic framework that generalizes dynamic programming to accommodate
many 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, can all be accommodated within the bucket elimination framework. Many probabilistic
inference tasks can likewise be expressed as bucket-elimination algorithms. These include:
belief updating, finding the most probable explanation, and expected utility maximization. These algorithms
share the same performance guarantees; all are time and space exponential in the inducedwidth
of the problem's interaction graph.
While elimination strategies have extensive demands on memory, a contrasting class of algorithms
called "conditioning search" require only linear space. Algorithms in this class split a problem into
subproblems by instantiating a subset of variables, called a conditioning set, or a cutset. Typical
examples of conditioning search algorithms are: backtracking (in constraint satisfaction), and branch
and bound (for combinatorial optimization).
The paper presents the bucket-elimination framework as a unifying theme across probabilistic and
deterministic reasoning tasks and show how conditioning search can be augmented to systematically
trade space for time.