Maximizing Submodular Set Function with Connectivity Constraint: Theory and ... - todo314 @ ウィキ

Maximizing Submodular Set Function with Connectivity Constraint: Theory and Application to Networks

• Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai
  • Research Center for Information Technology Innovation（資訊科技創新研究中心）
  • National Tsing Hua University（國立清華大學）
• INFOCOM 2013

概要

• ワイヤレスネットワークのルーターの設置問題
• submodular関数で表せる
• さらにルーターは連結であるという制約を追加
• この設定でも近似アルゴリズムが設計できる
  • 1/O(√k)近似
• 頂点に重みをつけたbudget版も考えた
• 実験：ヒューリスティクスより良いよ

モチベーション

• ワイヤレスネットワークのルーター
• 下の2つの評価を良くしたい
  • 被覆領域
  • スループット
• 現実的にはルーターは連結

問題

• 予算制約無し

Maximum Submodular set function (MS) problem

• max f(S)
• s.t. |S|≦k
• 1-1/e近似

Maximum Rooted Submodular set function (MRS) problem

• max f(S)
• s.t. |S|≦k, r∈S
• 予めrが入っているとしてgreedy

Maximum Connected Submodular set function (MCS) problem

• max f(S)
• s.t. |S|≦k, Sは連結

• 予算制約有り

Maximum Connected Submodular set function with Budget constraint (MCSB) problem

• max f(S)
• s.t. Σ_{s∈S}w(s)≦B, Sは連結

MCSの近似アルゴリズム

1. 各rについて
   • Vr = d(v,r)≦[√k]のvをとってくる
   • Vrについて√kだけ選ぶMRSを解く
   • 一番良いのをとっておく<r*, S_r*>
2. この時点で、[√k]の非連結な頂点が選ばれており、点r*を中心に距離が高々[√k]離れている
3. r*からS_r*の各頂点を結ぶ頂点をとってきてS_r*に追加
4. return S_r*

MCSBの近似アルゴリズム

1. 頂点に重みがついているので、辺に重みがつくようにグラフをちょっと変形
2. MCSのみたいに、距離[√B]以内の頂点をとってきてMRSBを求める
3. 一番良いのをとってきたら結ぶ
4. この時点で、総重みはw(r*)+B以下（ちょっとオーバー
5. 頑張って実行可能解に変形

応用

• Maximum Connected Coverage (MCC) problem
  • f(S) = |C(S)| = |{v | d(S,v)≦r}|としたMRS
• Maximum Throughput Connected Coverage (MTCC) problem
  • f(S) = T(S) = Σ_{v∈C(S)}max_{s∈S}T(v,s)
    • 距離r以内のルーターで一番スループットが良いのの和とった

結果

• 定理1: MCSはNP-complete
• 定理2: 提案アルゴリズムはMCSに対して1/O(√k)近似
• 定理3: MCCは1/O(√k)近似で解ける
• 定理4: MTCCは1/O(√k)近似で解ける
• 定理5: MCSBは1/[(Δ+1)O(√B)]近似で解ける

実験

• ユーザーの被覆(MCC)と総スループット(MTCC)を考える
• まずユーザーの位置を決める
  • 位置はZipf'lawに従う
• 実際の無線環境を想定して設定
• MCCについて
  • 比較はVandinのアルゴリズム
  • rootを1個指定したバージョンも
    • これはVandinに負けた(´・ω・`)
  • おかしい：rootを指定した結果で減少してる
• MTCCについて
  • Vandinは適用不可
  • かわりにヒューリスティクス
  • Our algorithm最強だぜ！！
• budget版もやったよ

まとめ

• √kのはちょっと面白いけど、普通に貪欲じゃ駄目なのかな？
  • 1個最大を選ぶ
  • 今の集合に隣接してるから一番イイのを選ぶ
• ぱっと見でsubmodularの性質を満たすと分かりそうだが、この定式化は新しいのかなあ？
• 実験はMTCCの方が適当に見えた
  • Kleinbergのinfluence maximizationも最初はヒューリスティクスしか無かったししょうがないのかな

INFOCOM submodular function wireless network

2013-11-15 00:36:24 (Fri)