Message Passing for Max-weight Indep endent Set
Sujay Sanghavi, Devavrat Shah, Alan Willsky Poster ID T45

We study max-product MWIS on general graphs. We · Show that if LP relaxation lo ose  max-product cannot converge. · Develop a certificate of optimality that can be checked at fixed-points of max-product. · Show that a simple two-sided mo dification of max-product always succeeds whenever LP relaxation is tight, · Show that any MAP estimation problem can be reduced to a MWIS problem.
5
3

= Both nodes cannot be "on" at same time.
1

3

Original Graph

Resulting Pairwise MRF