two new local search strategies for minimum vertex cover

ISCAS OpenIR

	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
会议录名称	Proceedings of the National Conference on Artificial Intelligence
页码	441-447
会议日期	July 22, 2012 - July 26, 2012
会议地点	Toronto, ON, Canada
收录类别	EI
ISBN	9781577355687
部门归属	(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
摘要	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.
关键词	Heuristic Algorithms Learning Algorithms
主办者	Association for the Advancement of Artificial Intelligence (AAAI); AI Journal; Steven Kuhn, Pine River Capital; National Science Foundation; Microsoft Research
语种	英语
内容类型	会议论文
URI标识	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],2012:441-447.