Show simple item record

dc.contributor.authorAlbrecht, A.
dc.contributor.authorLane, P.C.R.
dc.contributor.authorSteinhofel, K.
dc.date.accessioned2008-07-05T15:17:42Z
dc.date.available2008-07-05T15:17:42Z
dc.date.issued2008
dc.identifier.citationAlbrecht , A , Lane , P C R & Steinhofel , K 2008 , ' Estimating the Number of Local Maxima for k-SAT Instances ' , Procs , vol. 10 .
dc.identifier.otherPURE: 97144
dc.identifier.otherPURE UUID: 6f72eb92-a9e8-47e0-93af-82d039eca403
dc.identifier.otherdspace: 2299/2188
dc.identifier.urihttp://hdl.handle.net/2299/2188
dc.description.abstractWe explore the applicability of a sampling method devised by J. Garnier and L. Kallel (SIAM J. Discrete Math., 2002) to approximate the number of local maxima in search spaces induced by k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. Although the problem setting for k-SAT instances does not meet all pre-conditions required by the Garnier/Kallel-approach, we obtain approximations of the number of local maxima within the same order of magnitude as the exact values that have been determined by complete search. Since the comparison requires calculation of the complete --set of local maxima, only small k-SAT instances have --been considered so far. Furthermore, we outline a method for obtaining upper bounds for the average number of local maxima in k-SAT instances, which shows changes in the average number around the phase transition threshold.en
dc.language.isoeng
dc.relation.ispartofProcs
dc.titleEstimating the Number of Local Maxima for k-SAT Instancesen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionScience & Technology Research Institute
dc.description.statusPeer reviewed
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record