会议论文详细信息
ELC International Meeting on Inference, Computation, and Spin Glasses
Loop calculus and bootstrap-belief propagation for perfect matchings on arbitrary graphs
Chertkov, M.^1 ; Gelfand, A.^1,2 ; Shin, J.^3
Theoretical Division, Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM 87545, United States^1
Department of Computer Science, University of California, Irvine, Irvine, CA 92697-3435, United States^2
Mathematical Sciences Department, IBM T. J. Watson Research, Yorktown Heights, NY 10598, United States^3
关键词: Arbitrary graphs;    Belief propagation;    Bethe free energy;    Integer Linear Programming;    Partition functions;    Perfect matchings;    Problem formulation;    Zero temperatures;   
Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/473/1/012007/pdf
DOI  :  10.1088/1742-6596/473/1/012007
来源: IOP
PDF
【 摘 要 】

This manuscript discusses computation of the Partition Function (PF) and the Minimum Weight Perfect Matching (MWPM) on arbitrary, non-bipartite graphs. We present two novel problem formulations-one for computing the PF of a Perfect Matching (PM) and one for finding MWPMs-that build upon the inter-related Bethe Free Energy (BFE), Belief Propagation (BP), Loop Calculus (LC), Integer Linear Programming and Linear Programming frameworks. First, we describe an extension of the LC framework to the PM problem. The resulting formulas, coined (fractional) Bootstrap-BP, express the PF of the original model via the BFE of an alternative PM problem. We then study the zero-temperature version of this Bootstrap-BP formula for approximately solving the MWPM problem. We do so by leveraging the Bootstrap-BP formula to construct a sequence of MWPM problems, where each new problem in the sequence is formed by contracting odd-sized cycles (or blossoms) from the previous problem. This Bootstrap-and-Contract procedure converges reliably and generates an empirically tight upper bound for the MWPM. We conclude by discussing the relationship between our iterative procedure and the famous Blossom Algorithm of Edmonds '65 and demonstrate the performance of the Bootstrap-and-Contract approach on a variety of weighted PM problems.

【 预 览 】
附件列表
Files Size Format View
Loop calculus and bootstrap-belief propagation for perfect matchings on arbitrary graphs 573KB PDF download
  文献评价指标  
  下载次数:9次 浏览次数:28次