Show simple item record

dc.contributor.convenorAssociation for the Advancement of Artificial Intelligence
dc.contributor.authorCai, Shaowei
dc.contributor.authorSu, Kaile
dc.contributor.authorChen, Qingliang
dc.contributor.editorMaria Fox and David Poole
dc.date.accessioned2017-05-03T13:11:40Z
dc.date.available2017-05-03T13:11:40Z
dc.date.issued2010
dc.date.modified2011-06-06T06:04:10Z
dc.identifier.refurihttp://www.aaai.org/Conferences/AAAI/aaai10.php
dc.identifier.urihttp://hdl.handle.net/10072/39055
dc.description.abstractA 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.
dc.description.peerreviewedYes
dc.description.publicationstatusYes
dc.languageEnglish
dc.language.isoeng
dc.publisherAAAI Press
dc.publisher.placeUnited States
dc.publisher.urihttp://www.aaai.org/Conferences/AAAI/aaai10.php
dc.relation.ispartofstudentpublicationN
dc.relation.ispartofconferencenameThe Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10)
dc.relation.ispartofconferencetitleProceedings 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)
dc.relation.ispartofdatefrom2010-07-11
dc.relation.ispartofdateto2010-07-15
dc.relation.ispartoflocationAtlanta, Georgia, USA
dc.rights.retentionY
dc.subject.fieldofresearchArtificial intelligence not elsewhere classified
dc.subject.fieldofresearchcode460299
dc.titleEWLS: A new local search for Minimum Vertex Cover
dc.typeConference output
dc.type.descriptionE1 - Conferences
dc.type.codeE - Conference Publications
gro.date.issued2010
gro.hasfulltextNo Full Text
gro.griffith.authorSu, Kaile


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

  • Conference outputs
    Contains papers delivered by Griffith authors at national and international conferences.

Show simple item record