Multi-start iterated tabu search for the minimum weight vertex cover problem

作者：Zhou, Taoqing; Lu, Zhipeng; Wang, Yang; Ding, Junwen; Peng, Bo^*

来源：Journal of Combinatorial Optimization, 2016, 32(2): 368-384.

DOI：10.1007/s10878-015-9909-3

• Minimum weight vertex cover problem
• Tabu search
• Fast evaluation strategy
• Perturbation
• Meta-heuristic

The minimum weight vertex cover problem (MWVCP) is one of the most popular combinatorial optimization problems with various real-world applications. Given an undirected graph where each vertex is weighted, the MWVCP is to find a subset of the vertices which cover all edges of the graph and has a minimum total weight of these vertices. In this paper, we propose a multi-start iterated tabu search algorithm (MS-ITS) to tackle MWVCP. By incorporating an effective tabu search method, MS-ITS exhibits several distinguishing features, including a novel neighborhood construction procedure and a fast evaluation strategy. Extensive experiments on the set of public benchmark instances show that the proposed heuristic is very competitive with the state-of-the-art algorithms in the literature.

• 出版日期2016-8
• 单位华中科技大学