An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ... - todo314 @ ウィキ

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)近似アルゴリズムをお見せしますよ。」

FOCS

2013-11-03 03:02:58 (Sun)