.png){kind=icon}
返回
A population-based iterated greedy algorithm for the minimum weight vertex cover problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2012.02.013.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given an undirected, vertex-weighted graph, the goal of the minimum weight vertex cover problem is to find a subset of the vertices of the graph such that the subset is a vertex cover and the sum of the weights of its vertices is minimal. This problem is known to be NP-hard and no efficient algorithm is known to solve it to optimality. Therefore, most existing techniques are based on heuristics for providing approximate solutions in a reasonable computation time. Population-based search approaches have shown to be effective for solving a multitude of combinatorial optimization problems. Their advantage can be identified as their ability to find areas of the space containing high quality solutions. This paper proposes a simple and efficient population-based iterated greedy algorithm for tackling the minimum weight vertex cover problem. At each iteration, a population of solutions is established and refined using a fast randomized iterated greedy heuristic based on successive phases of destruction and reconstruction. An extensive experimental evaluation on a commonly used set of benchmark instances shows that our algorithm outperforms current state-of-the-art approaches. (C) 2012 Elsevier B. V. All rights reserved.
Keyword:
Iterated greedy algorithm
Minimum weight vertex cover problem
Population-based techniques
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.6
论文数:
1.4W
被引数:
4.8W
机构
查看更多机构
引用论文
An ant colony optimization algorithm for the minimum weight vertex cover problem求解最小权顶点覆盖问题的蚁群优化算法
.png){kind=icon}
PREAI
分享收藏An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem基于改进信息素校正策略的蚁群优化算法求解最小权顶点覆盖问题
PREAI
分享收藏
A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
PREAI
分享收藏 没有更多内容