Improved approximation for 3-dimensional matching via bounded pathwidth local search
-
k-Set packing
-
既存の
-
貪欲とか局所探索とか
-
あるkつ組を捨てれば、2つのkつ組をとれる、みたいな局所探索
-
2じゃなくてr以下とする
-
これ、FPTなんですか???
-
結果
-
FPT=W[1]でない限りf(r)poly(|F|)-timeは無い
-
交換の範囲を多項式個に制限
-
↑の判定をpath-widthで抑える
-
しかし近似比は変わらん!
FOCS
2013-11-03 02:32:18 (Sun)
最終更新:2013年11月03日 02:32