In this talk I will present a distributed anytime algorithm for performing MAP inference in graphical models. We devise a new formulation for the problem as a linear program relaxation over edges. This results in a constraint structure that enables the use of the Dantzig-Wolfe decomposition principle. The subprograms are defined over individual edges and can be computed in a distributed manner, thus allowing the solution of very large networks whose state space does not even fit in memory. The decomposition master program is guaranteed to compute the optimal solution in a finite number of iterations where the solution is monotonically converging. Experimental results show that our algorithm is an order of magnitude faster than current state of the art methods while achieving comparable accuracy.