The complexity of influence maximization problem in the deterministic linear ...

The complexity of influence maximization problem in the deterministic linear threshold model

  • Zaixin Lu, Wei Zhang, WeiliWu, Joonmo Kim, Bin Fu
  • Journal of Combinatorial Optimization 2012

概要だけ

  • linear threshold modelのしきい値を固定したバージョンを考える
  • 近似の難しさ
  • しきい値を固定するとσは多項式時間で求められる
    • 当たり前。なぜO(n^2)で求めている?
  • 何でこんなことをしたのか若干謎
最終更新:2014年01月24日 16:24