EWLS: A New Local Search for Minimum Vertex Cover
-
Shaowei Cai, Kaile Su, Qingliang Chen
-
AAAI 2010
概要
-
最小頂点被覆を求めたい
-
理論的には2近似は最高,1.3606未満はNP-hard
-
ヒューリスティック
-
辺重み付けと上界見積もりが新規な点
-
DIMACSとBHOSLIBで検証
動機付け
-
何故最小頂点被覆をしたいのか?
-
応用:ネットワークセキュリティ,スケジュール,VLSI設計
-
最大独立集合・最大クリークと関連がある(そのまんま)
-
SATはいい感じの手法が沢山→頂点被覆を変換すれば?→流石にでかすぎて
-
しょうがないので特化させた手法を作るよ
提案手法
-
cost(C) = Cで被覆してない辺の重みの総和
-
dscore(v,C) = cost(C)-cost(C')
-
C'=C-v or C+v の変化がある方
-
Cをvについて変化させた時の変化
-
score(u,v) = (Cのコスト)-(C-u+vのコスト)
-
これをどう使うのか?
-
score(u,v)>0 ならC-u+vとする価値があると判断
-
頂点被覆になってない集合Cについて
-
最適解のサイズは|C|+|Cで被覆されない辺|で上から抑えられる(上界)
概要
-
入力:G=(V,E), δ, maxstep
-
δの意味:常に|C|=上界-δとなるようにする
-
上界が更新される度にCが1小さくなる
-
C: 解
-
L: Cで被覆されない辺集合
-
UL⊆L: ↑の内チェックされてない
-
適当に頂点被覆を作り,δ捨てる
-
while step < maxstep
-
u削除,v追加なu,vを見つける(但し,前々の状態に戻らない)§
-
有:C←C-u+v,
-
無:L中の辺重み++,Cを適当に変える(局所解にハマった)
-
|C|+|L|<上界なら
-
上界更新
-
C*←Cから作った頂点被覆(Lの頂点を追加)
-
end
-
辺の重み更新は局所解にハマった時だけ更新
-
既存のアプローチはステップ毎
-
L中で最長老辺(v1*,v2*)について,u∈C, v=v1* or v2*, score(u,v)>0なu,vを返す
-
UL中で老いてる順に上と同じことをする
実験
-
DIMACS Clique Benchmark
-
めっちゃ密:|V|=4 000, |E|=4 000 268がほぼ最大
-
これならクリークのために補グラフとってもいいわけだ
-
BHOSLIB (Benchmark with Hidden Optimum Solutions)
-
評価指標
-
100回中最適解が得られた比率
-
最適解が得られた時の平均時間
-
PLS,COVERでは最適解が得られなかったもので得られたのがある
-
比率が良い
まとめ
-
scoreでキューに突っ込むとかはしないのね
-
局所解にハマるんかな
-
実験がベンチマーク次第という感じがして果てしなく微妙
-
比率で測るのか…
-
AAAIだからしょうがないけど,手法の挙動の実験的解析が無いから微妙なんだ…
AAAI 最小頂点被覆
2015/06/22 15:43
最終更新:2015年06月22日 15:48