Online Node-weighted Steiner Forest and Extensions via Disk Paintings - todo314 @ ウィキ

Online Node-weighted Steiner Forest and Extensions via Disk Paintings

• Mohammad Taghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi
• In FOCS 2013

• Online node-weighted steiner forest
  • min w(U)
  • s.t. G(U)は(s_1,t_1),…,(s_k,t_k)を連結にする
  • ↑はオフライン、これを更にオンラインにする
  • (s_i,t_i)が来た時には、1~iまでについて連結にする
• Online steiner tree
  • ターミナルが順番に来る
  • spider decompositionってのを考える
  • MSTを作っておいて、各辺を高々2回だけ、log nステップ
• 点重みの場合
  • 同じ点が一般使われる
  • Facility Locationに帰着

FOCS

2013-11-03 03:06:26 (Sun)