Poster M46: Linear Programming Analysis of Loopy Belief Propagation for Weighted Matching, S. Sanghavi, D. Malioutov, A. Willsky.

We analyze max-pro duct algorithm for weighted matching (WM) problems on general graphs. We show that max-product has close ties to LP relaxation of weighted matching: · LP relaxation tight  max-product convergent and correct, · LP relaxation loose  max-product does not converge.
b
1.1 1 1 1

a c c d
1.1

b d c a d d c b c

a d a

b c d

a

b

c

d

a

a

a

b

d

b

a

a

a

a

b

d

b

a

Proof uses alternating paths in the max-product computation tree, and perturbation arguments over the matching polytope.