two new local search strategies for minimum vertex cover
文献类型：会议论文
| 作者 | Cai Shaowei ; Su Kaile ; Sattar Abdul |
| 出版日期 | 2012 |
| 会议名称 | 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12 |
| 会议日期 | July 22, 2012 - July 26, 2012 |
| 会议地点 | Toronto, ON, Canada |
| 关键词 | Heuristic algorithms Learning algorithms |
| 页码 | 441-447 |
| 中文摘要 | In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-of-the-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved. |
| 英文摘要 | In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-of-the-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved. |
| 收录类别 | EI |
| 会议主办者 | Association for the Advancement of Artificial Intelligence (AAAI); AI Journal; Steven Kuhn, Pine River Capital; National Science Foundation; Microsoft Research |
| 会议录 | Proceedings of the National Conference on Artificial Intelligence
 |
| 语种 | 英语 |
| ISBN号 | 9781577355687 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/15864]  |
| 专题 | 软件研究所_软件所图书馆_会议论文 |
| 推荐引用方式 GB/T 7714 | Cai Shaowei,Su Kaile,Sattar Abdul. two new local search strategies for minimum vertex cover[C]. 见:26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12. Toronto, ON, Canada. July 22, 2012 - July 26, 2012. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。