KDD 2018 | Trajectory-driven Influential Billboard Placement
街頭広告をどのように選ぶかに取り組む。
問題設定としては
- 緯度経度で構成される軌跡 (trajectory) の集合
- 緯度軽度とコストで構成される街頭広告 (billboard) の集合
- 総予算
が与えられ、
- 軌跡 のいずれかの点が街頭広告 の半径 に入った時、確率 で影響を受ける (influenced)
- 街頭広告集合 に対する軌跡 への影響を とする
とするときに影響が最大になるように広告を選ぶ問題を解く。
方針としては「実データにおける多くの軌跡は短い領域の中に存在する」という観測にもとづき、同じ軌跡になるべくクラスタが被らないように街頭広告をクラスタリングして解く。
DP の話が出てきたので読むのを止めた。
こういう話結構昔からやられてそうだけど最適化の世界はよくわからない。詳しい人に解説してほしい。 (論文中では半径を考慮しなきゃいけないところが既存手法で対応していないらしい)