最小コストネットワークフローにおける信念伝播: 収束と正確性

いわゆる信念伝播アルゴリズムのようなメッセージパッシング型アルゴリズムは、最近、統計、信号処理、機械学習コミュニティにおいて、さまざまな最適化および推論問題を解決するための魅力的なアルゴリズムとして多くの注目を集めています。分散型で実装が容易かつ経験的に成功しているアルゴリズムであるBPは、理論的観点からも注目に値し、現在の時点ではあまり知られていません。このギャップを埋めるために、我々は、運用リサーチ分野における古典的な問題である定容量最小コストネットワークフロー問題の文脈におけるBPアルゴリズムの性能を考察します。我々は、基礎となる問題の最適解が一意であり、問題の入力が整数である限り、BPが擬似多項式時間で最適解に収束することを証明します。さらに、最適解の一意性を必要としない同じ問題に対する完全多項式時間ランダム近似スキーム（FPRAS）を提供するBPアルゴリズムの簡単な修正を示します。これにより、BPが完全多項式の実行時間を持つことが証明された初めての事例となります。我々の結果は、重要なクラスの最適化問題を解決するための魅力的な手法としてのBPの実現可能性に対する理論的な正当化を提供します。