EWLS: A New Local Search for Minimum Vertex Cover - todo314 @ ウィキ

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: ↑の内チェックされてない

1. 適当に頂点被覆を作り，δ捨てる
2. while step < maxstep
3. u削除，v追加なu,vを見つける（但し，前々の状態に戻らない）§
   1. 有：C←C-u+v，
   2. 無：L中の辺重み++，Cを適当に変える（局所解にハマった）
4. |C|+|L|<上界なら
   1. 上界更新
   2. C*←Cから作った頂点被覆（Lの頂点を追加）
5. end

• 辺の重み更新は局所解にハマった時だけ更新
• 既存のアプローチはステップ毎

• §の処理
• 被覆されない期間が長い程選ばれやすい

1. L中で最長老辺(v1*,v2*)について，u∈C, v=v1* or v2*, score(u,v)>0なu,vを返す
   • 少しでも良くなるなら最長老を加える
2. UL中で老いてる順に上と同じことをする
   • 前のステップとかでもう確認しちゃったら見ない

• δの効果
  • 大きすぎると，C*が微妙
  • 小さすぎると，？

実験

• DIMACS Clique Benchmark
  • めっちゃ密：|V|=4 000, |E|=4 000 268がほぼ最大
  • これならクリークのために補グラフとってもいいわけだ
• BHOSLIB (Benchmark with Hidden Optimum Solutions)
  • SAT'04コンテスト
  • こっちも密
• 評価指標
  • 100回中最適解が得られた比率
  • 最適解が得られた時の平均時間
• PLS，COVERでは最適解が得られなかったもので得られたのがある
• 比率が良い

まとめ

• scoreでキューに突っ込むとかはしないのね
• 局所解にハマるんかな
• 実験がベンチマーク次第という感じがして果てしなく微妙
• 比率で測るのか…
• AAAIだからしょうがないけど，手法の挙動の実験的解析が無いから微妙なんだ…

AAAI 最小頂点被覆

2015/06/22 15:43