Show simple item record

dc.contributor.authorAlbrecht, A.
dc.contributor.authorLane, P.C.R.
dc.contributor.authorSteinhofel, K.
dc.date.accessioned2011-11-21T13:01:07Z
dc.date.available2011-11-21T13:01:07Z
dc.date.issued2008
dc.identifier.citationAlbrecht , A , Lane , P C R & Steinhofel , K 2008 , Combinatorial landscape analysis for k-SAT instances . in IEEE Congress on Evolutionary Computation 2008 : CEC 2008 . vol. 2008 , Institute of Electrical and Electronics Engineers (IEEE) , pp. 2498-2504 , IEEE Congress on Evolutionary Computation 2008 , Hong Kong , Hong Kong , 1/06/08 . https://doi.org/10.1109/CEC.2008.4631133
dc.identifier.citationconference
dc.identifier.isbn978-1-4244-1822-0
dc.identifier.otherdspace: 2299/2416
dc.identifier.urihttp://hdl.handle.net/2299/7042
dc.description“This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder." “Copyright IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.” DOI: 10.1109/CEC.2008.4631133
dc.description.abstractOver the past ten years, methods from statistical physics have provided a deeper inside into the average complexity of hard combinatorial problems, culminating in a rigorous proof for the asymptotic behaviour of the k-SAT phase transition threshold by Achlioptas and Peres in 2004. On the other hand, when dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase might be helpful for an appropriate adjustment of local search-based procedures. In the present paper, we address both issues in the context of landscapes induced by k-SAT instances: Firstly, we utilize a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. Secondly, we outline a method for obtaining upper bounds for the average number of local maxima in k-SAT instances which indicates some kind of phase transition for the neighbourhood-specific ratio m/n = Θ(2k/k).en
dc.format.extent202124
dc.language.isoeng
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartofIEEE Congress on Evolutionary Computation 2008
dc.titleCombinatorial landscape analysis for k-SAT instancesen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionScience & Technology Research Institute
rioxxterms.versionofrecord10.1109/CEC.2008.4631133
rioxxterms.typeOther
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record