Analysis of Local Search Landscapes for k-SAT Instances

A. Albrecht, P.C.R. Lane, K. Steinhofel

    Research output: Contribution to journalArticlepeer-review

    7 Citations (Scopus)
    50 Downloads (Pure)


    Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise 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. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound [...] for the average number of local maxima, if m is in the region of 2 k · n/k. [...see original online abstract for correct notation]
    Original languageEnglish
    Pages (from-to)465-488
    JournalMathematics in Computer Science
    Issue number4
    Publication statusPublished - 2010


    Dive into the research topics of 'Analysis of Local Search Landscapes for k-SAT Instances'. Together they form a unique fingerprint.

    Cite this