Accelerating Message Passing for MAP with Benders Decomposition

Julian Yarkony, Shaofei Wang

We introduce a novel mechanism to tighten the local polytope relaxation for MAP inference in Markov random fields with low state space variables. We consider a surjection of the va…