Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free ... - todo314 @ ウィキ

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

• Joseph Cheriyan, Laszlo A. Vegh
• In FOCS 2013

• k-connectivity SNDP
  • min v(F)
  • s.t. (V,F)がk-connected
• 近似アルゴリズム
  • O(log k log n/(n-k))
    • k=n-o(n)の時やばお
  • O(k)
    • n>3k-3
    • iterative rouding
  • 6-近似
    • n≧k^3(k-1)+k ←かっこいい！！（この論文）
    • Ω(k^3)（福永さん）
• 何でノードだとめんどいの？
  • 頂点集合3つに分かれるから
  • 辺連結度だったら、S-Tの間の辺だけでいい
  • 頂点だと、S-Tの間に頂点が出てきてやばめ
• アイデア
  • ↑で出てくるような変なケースを前処理で消す（新しい？
  • 2近似を2回+iterative roudingの2近似で6近似

FOCS

2013-11-03 02:56:13 (Sun)