摘要翻译：
我们考虑在任意图上寻找最小权$\bm$-匹配的一般问题。证明了当问题的线性规划(LP)松弛没有分式解时，置信传播(BP)算法收敛到正确解。我们还证明了当LP松弛存在分数阶解时，可以用BP算法求解LP松弛。我们的证明是基于图复盖的概念，并推广了Bayati-Shah-Sharma2005和Huang-Jebara2007}的分析。这些结果在以下几个方面值得注意：（1）它是极少数证明BP算法在不受图结构约束的情况下是正确的。（2）同步和异步BP算法证明工作的变体；它是第一个证明异步BP算法在组合优化问题上收敛性和正确性的证明。
---
英文标题：
《Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its
  Relation to Linear Programs with Integer Solutions》
---
作者：
Mohsen Bayati, Christian Borgs, Jennifer Chayes, Riccardo Zecchina
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Information Theory        信息论
分类描述：Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
涵盖信息论和编码的理论和实验方面。包括ACM学科类E.4中的材料，并与H.1.1有交集。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Mathematics        数学
二级分类：Information Theory        信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--

---
英文摘要：
  We consider the general problem of finding the minimum weight $\bm$-matching on arbitrary graphs. We prove that, whenever the linear programming (LP) relaxation of the problem has no fractional solutions, then the belief propagation (BP) algorithm converges to the correct solution. We also show that when the LP relaxation has a fractional solution then the BP algorithm can be used to solve the LP relaxation. Our proof is based on the notion of graph covers and extends the analysis of (Bayati-Shah-Sharma 2005 and Huang-Jebara 2007}.   These results are notable in the following regards: (1) It is one of a very small number of proofs showing correctness of BP without any constraint on the graph structure. (2) Variants of the proof work for both synchronous and asynchronous BP; it is the first proof of convergence and correctness of an asynchronous BP algorithm for a combinatorial optimization problem.
---
PDF链接：
https://arxiv.org/pdf/0709.1190