「An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ...」の編集履歴（バックアップ）一覧はこちら

「An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ...」(2013/11/03 (日) 03:02:58) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
- Jochen Koenemann, Sina Sadeghian, Laura Sanità
- In FOCS 2013

- ノード重みはキテるんですよ！！

- Prize collecting node-weighted steiner tree
-- w:V→R+
-- p:V→R+
-- min w(V(T)) + P(V-V(T))
-- s.t. Tはtree
--- 左はスパンしている、右はしていない
- LMP: Lagrangian multiplier preserving
-- w(V(T))+αp(V-V(T))≦αw(V(T))+αp(V-V(T))
-- αがlog nってのが結果
-- 何でLMP？？？
--- 色々他の問題に使ったり出来て便利
-- 実は10年位前にlog n近似はある（STOC）、けど、それはマチガッテイル！！
-- 「10年間待ってください。本当のO(log n)近似アルゴリズムをお見せしますよ。」

&tags()

&update()