Two New Local Search Strategies for Minimum Vertex Cover

Two New Local Search Strategies for Minimum Vertex Cover

  • Shaowei Cai, Kaile Su, Abdul Sattar
  • AAAI 2012

概要

  • 最先端の手法=[Cai-Su-Chen AAAI'10]には2つの問題が有る
    • 頂点対の選択は時間がかかる
      • →2段階制にするよ!
    • 辺重みを減らす処理が無い
      • 遥か昔の重みが邪魔になるかも
      • →忘却を入れる
  • 上を解決したNuMVCを提案

提案手法

2段階交換

  • k-頂点被覆が手許にある→(k-1)-頂点被覆を探す
    • |C|=k-1のまま頂点を消す入れるを反復
    • (AAAI'10みたいな上界を使わんらしい)
  1. dscore最高の頂点uを取り除く
  2. 未被覆の辺eを無作為に選びdscoreの高い端点vを加える
  • |R|*|A|→|R|+|A|みたいに速くなることが期待できる

忘却付き辺重み付け

  • 平均重みが閾値γを超えたら,各重みをρ(<1)倍

NuMVC概要

  • Configuration Checking
    • vをCから削除後,近傍の(Cに入るかという意味での)状態が変わるまでvをCに再追加しない
      • 周りが変わってないと,vの近傍については何も変わってないから意味無さそうという直感
    • bool変数confを各頂点に用意するだけ
  1. if Cが頂点被覆になってる
    • Cからdscore最大の頂点を削除
  2. dscore最大の頂点uを選択
  3. C←C+u
  4. conf[v]でdscore最大の頂点vを選択
  5. C←C+v
  6. 未被覆の辺の重み++
  7. 平均重み≧γ なら,重み×←ρ

実験

  • ベンチマークは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