NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem

Authors

  • Ruizhi Li Jilin University of Finance and Economics
  • Shaowei Cai Institute of Software, Chinese Academy of Sciences
  • Shuli Hu Northeast Normal University
  • Minghao Yin Northeast Normal University
  • Jian Gao Dalian Maritime University

DOI:

https://doi.org/10.1609/aaai.v32i1.12137

Keywords:

minimum weighted vertex cover, local search, reduction rules, configuration checking with aspiration, self-adaptive vertex removing strategy

Abstract

The minimum weighted vertex cover (MWVC) problem is a well known combinatorial optimization problem with important applications. This paper 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, the configuration checking with aspiration is proposed to reduce cycling problem. Moreover, a self-adaptive vertex removing strategy is proposed to save time.

AAAI 2018 Proceedings Cover

Downloads

Published

2018-04-29

How to Cite

Li, R., Cai, S., Hu, S., Yin, M., & Gao, J. (2018). NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12137

Issue

Vol. 32 No. 1 (2018): Thirty-Second AAAI Conference on Artificial Intelligence

Section

Student Abstract Track