Multi-start iterated tabu search for the minimum weight vertex cover problem
Autor: | Yang Wang, Bo Peng, Junwen Ding, Zhipeng Lü, Taoqing Zhou |
---|---|
Rok vydání: | 2015 |
Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies Vertex cover Minimum weight 02 engineering and technology Edge cover Tabu search Computer Science Applications Vertex (geometry) Combinatorics Computational Theory and Mathematics Iterated function 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Feedback vertex set Guided Local Search MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
Zdroj: | Journal of Combinatorial Optimization. 32:368-384 |
ISSN: | 1573-2886 1382-6905 |
DOI: | 10.1007/s10878-015-9909-3 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |
načítá se...