  Much effort has been directed at algorithms for obtaining the highest
probability configuration in a probabilistic random field model known as the
maximum a posteriori (MAP) inference problem. In many situations, one could
benefit from having not just a single solution, but the top M most probable
solutions known as the M-Best MAP problem. In this paper, we propose an
efficient message-passing based algorithm for solving the M-Best MAP problem.
Specifically, our algorithm solves the recently proposed Linear Programming
(LP) formulation of M-Best MAP [7], while being orders of magnitude faster than
a generic LP-solver. Our approach relies on studying a particular partial
Lagrangian relaxation of the M-Best MAP LP which exposes a natural
combinatorial structure of the problem that we exploit.
