<P>We study the maximum weight matching (MWM) problem for general graphs through the max-product belief propagation (BP) and related Linear Programming (LP). The BP approach provides distributed heuristics for finding the maximum <I>a post...
http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
https://www.riss.kr/link?id=A107708140
2018
-
SCOPUS,SCIE
학술저널
1471-1480(10쪽)
0
상세조회0
다운로드다국어 초록 (Multilingual Abstract)
<P>We study the maximum weight matching (MWM) problem for general graphs through the max-product belief propagation (BP) and related Linear Programming (LP). The BP approach provides distributed heuristics for finding the maximum <I>a post...
<P>We study the maximum weight matching (MWM) problem for general graphs through the max-product belief propagation (BP) and related Linear Programming (LP). The BP approach provides distributed heuristics for finding the maximum <I>a posteriori</I> (MAP) assignment in a joint probability distribution represented by a graphical model (GM), and respective LPs can be considered as continuous relaxations of the discrete MAP problem. It was recently shown that a BP algorithm converges to the correct MAP/MWM assignment under a simple GM formulation of MWM, as long as the corresponding LP relaxation is tight. First, under the motivation for forcing the tightness condition, we consider a new GM formulation of MWM, say C-GM, using non-intersecting odd-sized cycles in the graph; the new corresponding LP relaxation, say C-LP, becomes tight for more MWM instances. However, the tightness of C-LP now does not guarantee such convergence and correctness of the new BP on C-GM. To address the issue, we introduce a novel graph transformation applied to C-GM, which results in another GM formulation of MWM, and prove that the respective BP on it converges to the correct MAP/MWM assignment, as long as C-LP is tight. Finally, we also show that C-LP always has half-integral solutions, which leads to an efficient BP-based MWM heuristic consisting of making sequential, “cutting plane”, modifications to the underlying GM. Our experiments show that this BP-based cutting plane heuristic performs, as well as that based on traditional LP solvers.</P>