QQ客服 官方微博 反馈留言

	Two weighting local search for minimum vertex cover
	Cai, Shaowei ; Lin, Jinkun ; Su, Kaile
	2015
英文摘要	Minimum Vertex Cover (MinVC) is a well known NP-hard combinatorial optimization problem, and local search has been shown to be one of the most effective approaches to this problem. State-of-the-art MinVC local search algorithms employ edge weighting techniques and prefer to select vertices with higher weighted score. These algorithms are not robust and especially have poor performance on instances with structures which defeat greedy heuristics. In this paper, we propose a vertex weighting scheme to address this shortcoming, and combine it within the current best MinVC local search algorithm NuMVC, leading to a new algorithm called TwMVC. Our experiments show that TwMVC outperforms NuMVC on the standard benchmarks namely DIMACS and BHOSLIB. To the best of our knowledge, TwMVC is the first MinVC algorithm that attains the best known solution for all instances in both benchmarks. Further, TwMVC shows superiority on a benchmark of real-world networks. Copyright ? 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; EI; 1107-1113; 2
语种	英语
出处	29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/436819]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Cai, Shaowei,Lin, Jinkun,Su, Kaile. Two weighting local search for minimum vertex cover. 2015-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。