Join-graph based cost-shifting schemes
  We develop several algorithms taking advantage of two common approaches for
bounding MPE queries in graphical models: minibucket elimination and
message-passing updates for linear programming relaxations. Both methods are
quite similar, and offer useful perspectives for the other; our hybrid
approaches attempt to balance the advantages of each. We demonstrate the power
of our hybrid algorithms through extensive empirical evaluation. Most notably,
a Branch and Bound search guided by the heuristic function calculated by one of
our new algorithms has recently won first place in the PASCAL2 inference
challenge.
