影響最大化問題

Last updated Unknown Edit Source

• 有向グラフと情報伝達確率が与えられて、「影響拡散」$σ(S)$を最大化させる
  • $σ(S)$は複雑なのでBDDでは解けない(NP困難)が、$1-1/e$ [近似]は可能 #近似アルゴリズム
• あるノードSから別のノードへのパスの集合は組み合わせ爆発起こす
  • なので、これをBDDに落とし込むことによって回避
    • 離散構造処理技術のパターン(フレームワーク)に沿う
  • 決定グラフ（BDD含む）の基本演算を用いれば、σ(S)の最大化ができる

#離散アルゴリズム