Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies

Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies

Shaowei Cai, Wenying Hou, Jinkun Lin, Yuanjie Li

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1412-1418. https://doi.org/10.24963/ijcai.2018/196

The minimum weight vertex cover (MWVC) problem is an important combinatorial optimization problem with various real-world applications. Due to its NP hardness, most works on solving MWVC focus on heuristic algorithms that can return a good quality solution in reasonable time. In this work, we propose two dynamic strategies that adjust the behavior of the algorithm during search, which are used to improve a state of the art local search for MWVC named FastWVC, resulting in two local search algorithms called DynWVC1 and DynWVC2. Previous MWVC algorithms are evaluated on graphs with random or hand crafted weights. In this work, we evaluate the algorithms on the vertex weighted graphs that obtained from an important real world problem, the map labeling problem. Experiments show that our algorithm obtains better results than previous algorithms for MWVC and maximum weight independent set (MWIS) on these real world instances. We also test our algorithms on massive graphs studied in previous works, and show significant improvements there.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Combinatorial Search and Optimisation