Finding Near-Optimal Independent Sets at Scale

arxiv.org

Yoichi Iwataに教えてもらった、MIS最強系の論文。Exactなアルゴリズムではないが、最適解がわかっているデータセットで軒並み最適解を出していて強い。

Kernelに遺伝的アルゴリズムを使用することを再帰的に行うアルゴリズム

Evolutionary Algorithm

1. 良さそうなIndependent Setの集合をいくつか見つける。
2. グラフの2-way-partitionを見つける。つまりseparatorを見つける
3. separateされた2要素を混ぜ合わせたものもIndependent Setになっている。これをmaximalにして、さらにARWアルゴリズムによって局所最適にする

これらを繰り返し、閾値以上の連続失敗で打ち切り

Kernelize

Akiba & Iwataのやつ。

1. Pendant degree 1のやつを確定させ、隣接のものを削除
2. degree 2-Folding 次数2の頂点があって、その隣接2頂点間に辺がないなら、foldできる
3. LP LPで解の上限を計算する。LPを解かなくても2部グラフのmaximum matchingで代用できる
4. Unconfined 忘れた
5. Twin なんだっけ
6. Alternative 初耳
7. Packing Akiba & Iwataのやつやな

Algorithm

まあ機械学習的には、上のアルゴリズムの

select の部分が次数をみているだけの適当っぽいので、ここを良くする、というアイデアはあるが、普通にクソ遅そう