EWLS: A new local search for Minimum Vertex Cover

There are no files associated with this record.

Title EWLS: A new local search for Minimum Vertex Cover
Author Cai, Shaowei; Su, Kaile; Chen, Qingliang
Publication Title Proceedings of the Twenty-fourth AAAI Conference on Artificial Intelligence and the Twenty-second Innovative Applications of Artificial Intelligence Conference, the First Symposium on Educational Advance (AAAI-10)
Editor Maria Fox and David Poole
Year Published 2010
Place of publication United States
Publisher AAAI Press
Abstract A number of algorithms have been proposed for the Minimum Vertex Cover problem. However, they are far from satisfactory, especially on hard instances. In this paper, we introduce Edge Weighting Local Search (EWLS), a new local search algorithm for the Minimum Vertex Cover problem. EWLS is based on the idea of extending a partial vertex cover into a vertex cover. A key point of EWLS is to find a vertex set that provides a tight upper bound on the size of the minimum vertex cover. To this purpose, EWLS employs an iterated local search procedure, using an edge weighting scheme which updates edge weights when stuck in local optima. Moreover, some sophisticated search strategies have been taken to improve the quality of local optima. Experimental results on the broadly used DIMACS benchmark show that EWLS is competitive with the current best heuristic algorithms, and outperforms them on hard instances. Furthermore, on a suite of difficult benchmarks, EWLS delivers the best results and sets a new record on the largest instance.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.aaai.org/Conferences/AAAI/aaai10.php
ISBN 9781577354635
Conference name The Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10)
Location Atlanta, Georgia, USA
Date From 2010-07-11
Date To 2010-07-15
URI http://hdl.handle.net/10072/39055
Date Accessioned 2011-04-20
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice