Local search with edge weighting and configuration checking heuristics for minimum vertex cover

File Size Format
71035_1.pdf 577Kb Adobe PDF View
Title Local search with edge weighting and configuration checking heuristics for minimum vertex cover
Author Cai, Shaowei; Su, Kaile; Sattar, Abdul
Journal Name Artificial Intelligence
Year Published 2011
Place of publication Netherlands
Publisher Elsevier BV
Abstract The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution. A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1016/j.artint.2011.03.003
Copyright Statement Copyright 2011 Elsevier. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. Please refer to the journal's website for access to the definitive, published version.
Volume 175
Issue Number 9-10
Page from 1672
Page to 1696
ISSN 0004-3702
Date Accessioned 2011-06-13
Date Available 2011-09-14T06:20:13Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
URI http://hdl.handle.net/10072/40810
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice