A natural linear programming (LP) relaxation of the problem exists. While the min-sum problem can be formulated as a linear optimization over the marginal polytope, the LP relaxation approximates this polytope by its outer bound, the local marginal polytope.
In this talk we will show that trying to find an efficient algorithm to solve the LP relaxation has a fundamental limitation. It is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure. Consequences of these results will be discussed.