Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow

Andrii Riazanov, Yury Maximov, Michael Chertkov

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize the formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.

    Original languageEnglish
    Title of host publication2018 Annual American Control Conference, ACC 2018
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages6108-6113
    Number of pages6
    ISBN (Print)9781538654286
    DOIs
    Publication statusPublished - 9 Aug 2018
    Event2018 Annual American Control Conference, ACC 2018 - Milwauke, United States
    Duration: 27 Jun 201829 Jun 2018

    Publication series

    NameProceedings of the American Control Conference
    Volume2018-June
    ISSN (Print)0743-1619

    Conference

    Conference2018 Annual American Control Conference, ACC 2018
    Country/TerritoryUnited States
    CityMilwauke
    Period27/06/1829/06/18

    Fingerprint

    Dive into the research topics of 'Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow'. Together they form a unique fingerprint.

    Cite this