Maximum weight matching using odd-sized cycles: Max-product belief propagation and half-integrality

Sungsoo Ahn, Michael Chertkov, Andrew E. Gelfand, Sejun Park, Jinwoo Shin

    Результат исследований: Вклад в журналСтатьярецензирование

    2 Цитирования (Scopus)


    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 a posteriori (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.

    Язык оригиналаАнглийский
    Страницы (с-по)1471-1480
    Число страниц10
    ЖурналIEEE Transactions on Information Theory
    Номер выпуска3
    СостояниеОпубликовано - мар. 2018


    Подробные сведения о темах исследования «Maximum weight matching using odd-sized cycles: Max-product belief propagation and half-integrality». Вместе они формируют уникальный семантический отпечаток (fingerprint).