Abstract. Dense, discrete Graphical Models with pairwise potentials are a powerful class of models which are employed in state-of-the-art computer vision
and bio-imaging applications. This work introduces a new MAP-solver, based
on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making
a small change to a low-performing solver, the Max Product Linear Programming (MPLP) algorithm [7], we derive the new solver MPLP++ that significantly
outperforms all existing solvers by a large margin, including the state-of-theart solver Tree-Reweighted Sequential (TRW-S) message-passing algorithm [17].
Additionally, our solver is highly parallel, in contrast to TRW-S, which gives a
further boost in performance with the proposed GPU and multi-thread CPU implementations. We verify the superiority of our algorithm on dense problems from
publicly available benchmarks as well as a new benchmark for 6D Object Pose
estimation. We also provide an ablation study with respect to graph density