Show simple item record

hal.structure.identifier
dc.contributor.authorGaspers, Serge*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifier
dc.contributor.authorOrdyniak, Sebastian*
hal.structure.identifier
dc.contributor.authorSaurabh, Saket*
hal.structure.identifier
dc.contributor.authorSzeider, Stefan*
dc.date.accessioned2013-09-12T10:15:37Z
dc.date.available2013-09-12T10:15:37Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11645
dc.language.isoenen
dc.subjectcombinatorial optimizationen
dc.subjectLocal Searchen
dc.subject.ddc006.3en
dc.titleDon't Be Strict in Local Search!en
dc.typeCommunication / Conférence
dc.description.abstractenLocal Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a na\"ive brute-force search of the k-exchange neighborhood requires n to the power of O(k) time, which is not practical even for very small values of k. Fellows et al. (IJCAI 2009) studied whether this brute-force search is avoidable and gave positive and negative answers for several combinatorial problems. They used the notion of local search in a strict sense. That is, an improved solution needs to be found in the k-exchange neighborhood even if a global optimum can be found efficiently. In this paper we consider a natural relaxation of local search, called permissive local search (Marx and Schlotter, IWPEC 2009) and investigate whether it enhances the domain of tractable inputs. We exemplify this approach on a fundamental combinatorial problem, Vertex Cover. More precisely, we show that for a class of inputs, finding an optimum is hard, strict local search is hard, but permissive local search is tractable. We carry out this investigation in the framework of parameterized complexity.en
dc.relation.ispartoftitleProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligenceen
dc.relation.ispartofeditorSelman, Bart
dc.relation.ispartofeditorHoffmann, Jörg
dc.relation.ispartofpublnameAAAI Pressen
dc.relation.ispartofdate2012
dc.identifier.urlsitehttp://arxiv.org/abs/1208.1688v3en
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-1-57735-568-7en
dc.relation.conftitleAAAI 2012en
dc.relation.confdate2012-07
dc.relation.confcityTorontoen
dc.relation.confcountryCanadaen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01496459*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record