Mini-Buckets: A General Scheme for Generating Approximations in Automated Reasoning

Abstract

The class of algorithms for approximating reasoning tasks presented in this paper is based on approximating the general bucket elimination framework. The algorithms have adjustable levels of accuracy and efficiency, and they can be applied uniformly across many areas and problem tasks. We introduce these algorithms in the context of combinatorial optimization and probabilistic inference. 1 Overview Bucket elimination is a unifying algorithmic framework that generalizes dynamic programming to enable many complex problem-solving and reasoning activities. Among the algorithms that can be accommodated within this framework are directional resolution for propositional satisfiability [ Dechter and Rish, 1994 ] , adaptive consistency for constraint satisfaction [ Dechter and Pearl, 1987 ] , Fourier and Gaussian elimination for linear inequalities [ Lassez and Mahler, 1992 ] , and dynamic programming for combinatorial optimization [ Bertele and Brioschi, 1972 ] . Many algorithms for probabil...