I will describe the potential of two known bounding approximation schemes for finding maximum likelihood solutions (MAP) in graphical models. One is the mini-bucket algorithm which relaxes the input problem using selective node duplication only, yielding single iteration message-passing structures. The other utilizes linear programming relaxations ideas to optimize cost-shifting schemes,  yielding iterative message-passing algorithms. I will show how the two ideas combined can yield tighter bounding procedures for MAP and demonstrate their potential both as stand-alone schemes, and as advise-giving heuristics within guiding systematic branch and bound search.