Message-passing for Graph-structured Linear Programs

Linear programming relaxations are one promising approach to solving the MAP estimation problem in Markov random fields; in particular, a body of past work has focused on the first-order tree-based LP