Institutional Repository
| two new local search strategies for minimum vertex cover | |
| Cai Shaowei; Su Kaile; Sattar Abdul | |
| 2012 | |
| Conference Name | 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12 |
| Source | Proceedings of the National Conference on Artificial Intelligence |
| Pages | 441-447 |
| Conference Date | July 22, 2012 - July 26, 2012 |
| Conference Place | Toronto, ON, Canada |
| Indexed Type | EI |
| ISBN | 9781577355687 |
| Department | (1) Key Laboratory of High Confidence Software Technologies Peking University Beijing China; (2) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China; (3) Institute for Integrated and Intelligent Systems Griffith University Brisbane QLD Australia; (4) ATOMIC Project Queensland Research Lab. NICTA Australia |
| English Abstract | 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. |
| Keyword | Heuristic Algorithms Learning Algorithms |
| Sponsorship | Association for the Advancement of Artificial Intelligence (AAAI); AI Journal; Steven Kuhn, Pine River Capital; National Science Foundation; Microsoft Research |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15864 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Cai Shaowei,Su Kaile,Sattar Abdul. two new local search strategies for minimum vertex cover[C],2012:441-447. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment