「Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free ...」の編集履歴（バックアップ）一覧はこちら

「Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free ...」(2013/11/03 (日) 02:56:13) の最新版変更点

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

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

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近似

&tags()

&update()