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

详细信息    查看全文

• 作者：Taoqing Zhou ; Zhipeng Lü ; Yang Wang ; Junwen Ding…
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：32
• 期：2
• 页码：368-384
• 全文大小：853 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886
• 卷排序：32

文摘

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.KeywordsMinimum weight vertex cover problemTabu search Fast evaluation strategyPerturbationMeta-heuristic