English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For the minimum cardinality vertex cover and maximum cardinality matchingproblems, the max-product form of belief propagation (BP) is known to performpoorly on general graphs. In this paper, we present an iterative loopyannealing BP (LABP) algorithm which is shown to converge and to solve a LinearProgramming relaxation of the vertex cover or matching problem on generalgraphs. LABP finds (asymptotically) a minimum half-integral vertex cover (henceprovides a 2-approximation) and a maximum fractional matching on any graph. Wealso show that LABP finds (asymptotically) a minimum size vertex cover for anybipartite graph and as a consequence compute the matching number of the graph.Our proof relies on some subtle monotonicity arguments for the local iteration.We also show that the Bethe free entropy is concave and that LABP maximizes it.Using loop calculus, we also give an exact (also intractable for generalgraphs) expression of the partition function for matching in term of the LABPmessages which can be used to improve mean-field approximations.

Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation