An efficient local search framework for the minimum weighted vertex cover problem

作者：Li, Ruizhi; Hu, Shuli; Zhang, Haochen; Yin, Minghao^*

来源：Information Sciences, 2016, 372: 428-445.

DOI：10.1016/j.ins.2016.08.053

• Minimum weighted vertex cover
• Weighted configuration checking
• Scoring strategy
• Local search
• Massive graph instances

The minimum weighted vertex cover (MWVC) problem, an extension of the classical minimum vertex cover (MVC) problem, is an important NP-complete combinatorial optimization problem with a wide range of applications. The objective of this paper is to design an efficient local search algorithm to solve the MWVC problem. First, the weighted edge strategy is proposed to define the dynamic scoring strategy so that our algorithm can find different possible optimal solutions. Second, the weighted configuration checking (WCC) strategy is proposed to overcome the cycling problem in local search. By combining the WCC strategy with the scoring strategy, we design the vertex selection strategy to determine the vertex to be selected as a candidate solution component. Based on these strategies, a novel local search framework, namely diversion local search based on weighted configuration checking (DLSWCC), is presented. DLSWCC is evaluated against several state-of-the-art algorithms on various benchmark instances. Experimental results show that DLSWCC outperforms its competitors in terms of both solution quality and computational efficiency in most classical instances. Specifically, DLSWCC can obtain 22 new upper bounds of 71 moderate-scale problem instances, 5 new upper bounds of 15 large-scale problem instances, and 56 new upper bounds of 56 massive graph instances.

• 出版日期2016-12-1
• 单位东北师范大学