Rounded Dynamic Programming for Tree-Structured Stochastic Network Design

Rounded Dynamic Programming for Tree-Structured Stochastic Network Design

  • Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein
  • AAAI 2014
  • Xiaojian WuにはAAAIでお会いした
  • このグループはあくまでStochastic Network Designとして捉えているっぽい(影響最大化も)

概要

  • 有向木上の確率的ネットワーク設計に対する丸め動的計画法
  • 河のネットワークでの状況を想定できるらしい
  • FPTASでO(n^2/ε^2)だけど実験的にはもう少し速い(し精度も良い)

動機付けとか

  • リバーネットワーク(?)の階層的構造を木構造で表現
  • その応用は障害除去による保全計画
  • 頂点に拡散する確率が分かってこれが目的関数
  • O’Hanley and Tomberlin (2005)が主となる先行研究らしい
    • 擬多項式時間のDP
    • コストが整数という制約

問題定義

  • fish barrier removal problem (魚の障害除去問題)
  • 色々取り除いて魚が通りやすくしたい
  • 魚達は木T=(V,E)を辿りソース(海)sを目指す
  • 各頂点は障害u⊆Bか合流点u⊆V\B
  • 魚は障害uを確率p_uで通れる
  • 各頂点にはいくつかの修復行動A_uがあって,aを使うとコストc_uaで確率がp_u|aに上昇
  • 行動の方策πが固定され下でのアクセス性P^+_{u|π}(めんどいので以下略)とは
    • sからuまで障害を上って来れる確率
  • もっと一般に$$ P^+_{v \rightarrow u \mid \pi} $$をvからuへの確率
  • 頂点には報酬r_uがある
  • 目的関数は$$ z(\pi) = \sum_{u \in V}P^+_{u \mid \pi}\cdot r_u $$
  • 予算b以内でz(π)を最大化する方策を見つけたい
  • uを根とする部分木については,以下で計算可
  • $$ z_u(\pi) = p_{u \mid \pi}\left( r_u + \sum_{v \in Ch(u)}z_v(\pi) \right) $$
  • live-edge による考え方
    • 各頂点を割り当てられた確率で残す
    • sから到達可能な報酬を集めればその期待値がz
    • KKTの影響最大化に当てはめると辺の確率を上げる

提案手法

  • Vazirani 2003 Approximation Algorithms を拡張?
  • 大事なこと:
  • 子供が高々2個になるように木を等価に変形できる
  • C_u(z) := 部分木T_uの期待報酬がzぴったりになるための最小コスト
  • uでの行動を固定すると,
    • (uの行動コスト)+(T_vでdにするコスト)+(T_wでz_{u,a}-dにするコスト)
    • をdについて回して最小コストをとればOK
    • v,wはuの子供
  • これだけだと指数的にエントリが増えちゃうのでやばい
    because the z values are real numbers, and
    the number of z values that must be evaluated increases exponentially
    as the recurrence approaches the source
    
  • zをKでスケールダウンさせてKの倍数に丸める
  • あとはゴリゴリ計算

解析

  • (1-ε)近似でO(n^2/ε^2)時間
  • 仮定: r_uの下界と上界を定数としている(・o・)
  • あんまり真面目に読んでないので謎

実験

  • 計算時間
    • 予算に対して普通のDPは超遅いよ,RDPは爆速
  • 時間とパラメータの解析もしている
    • 適切に設定すると超爆速だけど精度も90%以上とかになってる
    • 計算時間がドカッと下がる
  • どうやら実データだとnに対して線形に近い挙動っぽい?
  • 実際のネットワークで実験して図を示しているのが面白い

まとめ

  • こういう問題見つけてくるのすごいな
  • 問題見つけてくれば後はどうにかなりそう

AAAI ネットワーク設計

2014-09-24 00:32:53 (Wed)

最終更新:2014年09月24日 00:32