We consider the linear programming (LP) relaxation of the maximum a posteriori (MAP) inference problem in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based proximal function, which makes each subproblem in ADMM easy to solve in parallel using the sum-product algorithm. We show that Bethe-ADMM is guaranteed to converge globally for the MAP-LP problem. Further, the parallel Bethe-ADMM is shown to scale linearly with increasing number of cores, and can solve inference problems with millions of variables in less than a minute using 1000 cores.