Improved approximation for 3-dimensional matching via bounded pathwidth ... - todo314 @ ウィキ

Improved approximation for 3-dimensional matching via bounded pathwidth local search

• Marek Cygan
  • あのMarek Cygan
• In FOCS 2013

• k-Set packing
  • kの最大マッチングのようなもの
• 既存の
  • 貪欲とか局所探索とか
  • あるkつ組を捨てれば、2つのkつ組をとれる、みたいな局所探索
  • 2じゃなくてr以下とする
  • これ、FPTなんですか？？？
• 結果
  • FPT=W[1]でない限りf(r)poly(|F|)-timeは無い
  • 交換の範囲を多項式個に制限
  • ↑の判定をpath-widthで抑える
  • しかし近似比は変わらん！

FOCS

2013-11-03 02:32:18 (Sun)