「EWLS: A New Local Search for Minimum Vertex Cover」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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中で老いてる順に上と同じことをする
-- 前のステップとかでもう確認しちゃったら見ない
- δの効果
-- 大きすぎると，C*が微妙
-- 小さすぎると，？
* 実験
- DIMACS Clique Benchmark
-- めっちゃ密：|V|=4 000, |E|=4 000 268がほぼ最大
-- これならクリークのために補グラフとってもいいわけだ
- BHOSLIB (Benchmark with Hidden Optimum Solutions)
-- SAT'04コンテスト
-- こっちも密
- 評価指標
-- 100回中最適解が得られた比率
-- 最適解が得られた時の平均時間
- PLS，COVERでは最適解が得られなかったもので得られたのがある
- 比率が良い
* まとめ
- scoreでキューに突っ込むとかはしないのね
- 局所解にハマるんかな
- 実験がベンチマーク次第という感じがして果てしなく微妙
- 比率で測るのか…
- AAAIだからしょうがないけど，手法の挙動の実験的解析が無いから微妙なんだ…
&tags()
2015/06/22 15:43
