  This paper presents a new anytime algorithm for the marginal MAP problem in
graphical models. The algorithm is described in detail, its complexity and
convergence rate are studied, and relations to previous theoretical results for
the problem are discussed. It is shown that the algorithm runs in
polynomial-time if the underlying graph of the model has bounded tree-width,
and that it provides guarantees to the lower and upper bounds obtained within a
fixed amount of computational resources. Experiments with both real and
synthetic generated models highlight its main characteristics and show that it
compares favorably against Park and Darwiche's systematic search, particularly
in the case of problems with many MAP variables and moderate tree-width.
