An efficient local search framework for the minimum weighted vertex cover problem
An efficient local search framework for the minimum weighted vertex cover problem
复制标题
最小加权顶点覆盖问题的高效局部搜索框架
DOI：
10.1016/j.ins.2016.08.053
复制
发表时间：
2016
影响因子：
8.1
通讯作者：
Yin Minghao
中科院分区：
文献类型：
--
作者：
Li Ruizhi;Hu Shuli;Zhang Haochen;Yin Minghao
最小加权顶点覆盖（MWVC）问题是经典最小顶点覆盖（MVC）问题的推广，是一个重要的NP完全组合优化问题，有着广泛的应用。本文的目的是设计一个有效的局部搜索算法来解决MWVC问题。首先，提出了加权边策略来定义动态评分策略，使算法能够找到不同的可能最优解。其次，提出了加权配置检查（WCC）策略来克服局部搜索中的循环问题。结合WCC策略和评分策略，设计了顶点选择策略，确定待选顶点作为候选解组件。在此基础上，提出了一种新的局部搜索框架，即基于加权配置检查的分流局部搜索（DLSWCC）。DLSWCC在各种基准测试实例上针对几种最先进的算法进行了评估。实验结果表明，DLSWCC优于其竞争对手的解决方案质量和计算效率在大多数经典的情况下。具体而言，DLSWCC可以获得71个中等规模问题实例的22个新上界，15个大规模问题实例的5个新上界，以及56个海量图实例的56个新上界。
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.