Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs
| dc.creator | Sanghavi, Sujay | |
| dc.date | 2007-05-05 | |
| dc.date.accessioned | 2026-07-07T08:16:02Z | |
| dc.date.available | 2026-07-07T08:16:02Z | |
| dc.description | Max-product belief propagation is a local, iterative algorithm to find the mode/MAP estimate of a probability distribution. While it has been successfully employed in a wide variety of applications, there are relatively few theoretical guarantees of convergence and correctness for general loopy graphs that may have many short cycles. Of these, even fewer provide exact ``necessary and sufficient'' characterizations. In this paper we investigate the problem of using max-product to find the maximum weight matching in an arbitrary graph with edge weights. This is done by first constructing a probability distribution whose mode corresponds to the optimal matching, and then running max-product. Weighted matching can also be posed as an integer program, for which there is an LP relaxation. This relaxation is not always tight. In this paper we show that \begin{enumerate} \item If the LP relaxation is tight, then max-product always converges, and that too to the correct answer. \item If the LP relaxation is loose, then max-product does not converge. \end{enumerate} This provides an exact, data-dependent characterization of max-product performance, and a precise connection to LP relaxation, which is a well-studied optimization technique. Also, since LP relaxation is known to be tight for bipartite graphs, our results generalize other recent results on using max-product to find weighted matchings in bipartite graphs. | |
| dc.description | 6 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/0705.0760 | |
| dc.identifier | http://arxiv.org/abs/0705.0760 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133646 | |
| dc.subject | Information Theory | |
| dc.subject | Artificial Intelligence | |
| dc.subject | Machine Learning | |
| dc.subject | Networking and Internet Architecture | |
| dc.title | Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs | |
| dc.type | text |