  We present a distributed anytime algorithm for performing MAP inference in
graphical models. The problem is formulated as a linear programming relaxation
over the edges of a graph. The resulting program has a constraint structure
that allows application of the Dantzig-Wolfe decomposition principle.
Subprograms are defined over individual edges and can be computed in a
distributed manner. This accommodates solutions to graphs whose state space
does not fit in memory. The decomposition master program is guaranteed to
compute the optimal solution in a finite number of iterations, while the
solution converges monotonically with each iteration. Formulating the MAP
inference problem as a linear program allows additional (global) constraints to
be defined; something not possible with message passing algorithms.
Experimental results show that our algorithm's solution quality outperforms
most current algorithms and it scales well to large problems.
