Two New Local Search Strategies for Minimum Vertex Cover
-
Shaowei Cai, Kaile Su, Abdul Sattar
-
AAAI 2012
概要
-
最先端の手法=[Cai-Su-Chen AAAI'10]には2つの問題が有る
-
頂点対の選択は時間がかかる
-
辺重みを減らす処理が無い
-
上を解決したNuMVCを提案
提案手法
2段階交換
-
k-頂点被覆が手許にある→(k-1)-頂点被覆を探す
-
|C|=k-1のまま頂点を消す入れるを反復
-
(AAAI'10みたいな上界を使わんらしい)
-
dscore最高の頂点uを取り除く
-
未被覆の辺eを無作為に選びdscoreの高い端点vを加える
-
|R|*|A|→|R|+|A|みたいに速くなることが期待できる
忘却付き辺重み付け
NuMVC概要
-
Configuration Checking
-
vをCから削除後,近傍の(Cに入るかという意味での)状態が変わるまでvをCに再追加しない
-
周りが変わってないと,vの近傍については何も変わってないから意味無さそうという直感
-
bool変数confを各頂点に用意するだけ
-
if Cが頂点被覆になってる
-
dscore最大の頂点uを選択
-
C←C+u
-
conf[v]でdscore最大の頂点vを選択
-
C←C+v
-
未被覆の辺の重み++
-
平均重み≧γ なら,重み×←ρ
実験
-
ベンチマークはAAAI'10と同じ
-
DIMACSは提案手法では駄目で,PLSが解けてたりする
-
BHOSLIBはEWCC[Cai-Su-Sattar 2010]より僅かな改善
-
frb100-40というインスタンスが激ムズらしい
-
最適値が3900だが,3902,≦3903の比率で競っている…
まとめ
-
これでAAAI通るんだなあという感じ
-
性能(微妙に見える)だけで通るなら,もっとcleverな方法で強くすればいいんじゃね?
AAAI 最小頂点被覆
2015/06/22 16:23
最終更新:2015年06月22日 16:25