Why approximate when you can get the exact? Optimal Targeted Viral Marketing ... - todo314 @ ウィキ

Why approximate when you can get the exact? Optimal Targeted Viral Marketing at Scale

• Xiang Li, J. David Smith, Thang N. Dinh, My T. Thai
• INFOCOM 2017

概要

• 普通に厳密解目指すんで、オレ。
• RR集合をサンプルしてからMaxCover部分を整数計画ソルバで解く
  • 得られた結果の精度を保証するのがミソ

普通の

• いわゆるtwo-stage stochastic programmingを使った場合
  1. 各サンプルがO(m)サイズ
  2. 信頼区間だけなのが嫌だ
  3. $$(\epsilon,\delta)$$近似を保証するサンプルサイズが良く分からん

提案手法 Tiny Integer Program with Theoretically OPtimal results $$ \mathrm{T{\scriptsize IP}T{\scriptsize OP}} $$

• D-SSAの場合: 探索（速い貪欲算法）と検証は同サイズのRR集合で実施
• サンプルサイズのトレードオフが大事
  1. 整数計画: とても重い
  2. 検証: 速い
• 整数計画はとても普通のやり方
• 検証とサイズ増加のやり方
  • 驚くほどごちゃごちゃしている
  • 結局整数計画ソルバの吐いた解について、(ソルバに使ったRでのInf)≒(別のRでのInf)ならOKと判断する
  • なんとなくRademacher Averageっぽい？
  • サイズ増加は倍々ではなくて少し工夫している

実験

• 辺確率：1/入次数
  • そうしないと、RR集合が大きくなりすぎますからね( ･´ω･`)
• 比較手法：BCT, IMM, SSA
• Fig.7：何かTipTopの質悪くね？

まとめ

• やっぱり貪欲でいいのでは？
• それか整数計画に頼らない頑張りMaxCoverソルバ

INFOCOM 影響最大化

2017/10/02