Approximate Decomposition: A Method for Bounding and Estimating
  Probabilistic and Deterministic Queries
  In this paper, we introduce a method for approximating the solution to
inference and optimization tasks in uncertain and deterministic reasoning. Such
tasks are in general intractable for exact algorithms because of the large
number of dependency relationships in their structure. Our method effectively
maps such a dense problem to a sparser one which is in some sense "closest".
Exact methods can be run on the sparser problem to derive bounds on the
original answer, which can be quite sharp. We present empirical results
demonstrating that our method works well on the tasks of belief inference and
finding the probability of the most probable explanation in belief networks,
and finding the cost of the solution that violates the smallest number of
constraints in constraint satisfaction problems. On one large CPCS network, for
example, we were able to calculate upper and lower bounds on the conditional
probability of a variable, given evidence, that were almost identical in the
average case.
