Two Weighting Local Search for Minimum Vertex Cover

Two Weighting Local Search for Minimum Vertex Cover

  • Shaowei Cai, Jinkun Lin, Kaile Su
  • AAAI 2015

概要

  • AAAI'12の改良
  • 貪欲ヒューリスティックを頃すような入力に対して弱い
  • 頂点重み付で↑を解決(何で?)
  • 提案手法TwMCV(NuMVCの改良)
  • DIMACS+BHOSLIB+実世界ネットワーク(!)

提案手法

  • NuMVCと同じ枠組み
    • Cが頂点被覆になったら1頂点削除
    • 交換: C←C-u+v

頂点重み付け

  • Cにあまりいないような頂点を強制的にCに入れるようにする
  • 貪欲ヒューリスティックだと全く選ばれない頂点が必要なインスタンスに効果有りそう
  • 重み増加
    • 交換終了時にv \not \in Cについて,wv(v)++
  • 重み減少
    • 辺を選んで端点のscoreの差が超大きい時にvを選びCに追加,wv(v)←βwv(v)
  • 既存の手法との違い
    1. 頂点重み付け
      • 既存:まとめて減らす(←最近の結果を使いたいという動機)
      • 提案:1頂点(←こいつが繰り返して大量に選ばれることを防ぎたい)
    2. 「選ばれる特権として重みが使われたら」減らす
    3. 2頂点の重みに極端な差があったら←NEW!

TwMVC

  1. score最大の頂点uを選びCから削除
  2. 未被覆の辺eを無作為に選択
  3. v←§(e),Cにv追加
  4. 未被覆の辺eについてwe(e)++
  5. v \not \in Cについてwv(v)++
  6. 適当な周期で:we(e)>1ならwe(e)--
  7. 適当な周期で:wv(v)>1ならwv(v)--
  • §の処理
    1. Configuration的な意味で選択の余地が無い
    2. 頂点重みがδ以上違う
      • 大きい頂点vを返し,wv(v)*=β
    3. scoreで決める

実験

  • 比較対象:NuMVCだけ
  • DIMACS
    • brock800_2/_4で最適解が出るようになった
  • BHOSLIB
    • ちょっと速くなったかも位?
  • Webグラフ
    • www.graphrepository.comなるところから…
    • 最大でweb-uk-2005が|E|=11.7M(???)
    • 突然被覆の大きさの平均で比較し始めたぞ…
  • 最大クリーク手法との比較
    • [Li-Quan 2010]と[Li-Fang-Xu 2013]
    • 何か全体的に速そう
    • 密なので補グラフg(ry

まとめ

  • 比較対象がNuMVCだけなのが驕り高ぶり感ある
  • 以前のはジャーナル版あるし,そっちも(あれば)チェックしたほうが良さそう

AAAI 最小頂点被覆

2015/06/22

最終更新:2015年06月22日 17:07