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関数で表せる
-
さらにルーターは連結であるという制約を追加
-
この設定でも近似アルゴリズムが設計できる
-
頂点に重みをつけた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の近似アルゴリズム
-
各rについて
-
Vr = d(v,r)≦[√k]のvをとってくる
-
Vrについて√kだけ選ぶMRSを解く
-
一番良いのをとっておく<r*, S_r*>
-
この時点で、[√k]の非連結な頂点が選ばれており、点r*を中心に距離が高々[√k]離れている
-
r*からS_r*の各頂点を結ぶ頂点をとってきてS_r*に追加
-
return S_r*
MCSBの近似アルゴリズム
-
頂点に重みがついているので、辺に重みがつくようにグラフをちょっと変形
-
MCSのみたいに、距離[√B]以内の頂点をとってきてMRSBを求める
-
一番良いのをとってきたら結ぶ
-
この時点で、総重みはw(r*)+B以下(ちょっとオーバー
-
頑張って実行可能解に変形
応用
-
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)を考える
-
まずユーザーの位置を決める
-
実際の無線環境を想定して設定
-
MCCについて
-
比較はVandinのアルゴリズム
-
rootを1個指定したバージョンも
-
おかしい: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)
最終更新:2013年11月15日 00:36