NuMWVC: A novel local search for minimum weighted vertex cover problem. Issue 9 (1st September 2020)

• Record Type: Journal Article
• Authors: Li, Ruizhi; Hu, Shuli; Cai, Shaowei; Gao, Jian; Wang, Yiyuan; Yin, Minghao
• Is Part Of: Journal of the Operational Research Society. Volume 71:Issue 9(2020)
• Page Start: 1498
• Page End: 1509
• Publication Date: 2020-09-01
• Subjects: Minimum weighted vertex cover problem -- local search -- heuristic search; Operations research -- Periodicals; 658.4034
• DOI: 10.1080/01605682.2019.1621218
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: The problem of finding a minimum weighted vertex cover (MWVC) in a graph is a well-known combinatorial optimisation problem with important applications. This article introduces a novel local search algorithm called NuMWVC for MWVC based on three ideas. First, four reduction rules are introduced during the initial construction phase. Second, a strategy called configuration checking with aspiration, which aims for reducing cycling in local search, is proposed for MWVC for the first time. Moreover, a self-adaptive vertex removing strategy is proposed to save time spent on searching solutions for which the quality is likely far from optimality. Experimental results show that NuMWVC outperforms state-of-the-art local search algorithms for MWVC on the standard benchmarks, massive graphs and real-world problem (map labeling problem) instances.