Many important combinatorial optimization problems can be expressed as
constraint satisfaction problems
. When problems are too difficult to be solved exactly, approximation methods become the best option.
(MBE) is a well known approximation method for combinatorial optimization problems. It has a control parameter
that allow us to trade time and space for accuracy. In practice it is the space and not the time that limits the execution with high values of
. In this paper we introduce a set of improvements on the way MBE handles memory. The resulting algorithm dfMBE may be orders of magnitude more efficient. As a consequence, higher values of
can be used which, in turn, yields significantly better bounds. We demonstrate our approach in scheduling, probabilistic reasoning and resource allocation problems.