Combinatorial landscape analysis for k-SAT instances

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    8 Citations (Scopus)
    73 Downloads (Pure)

    Abstract

    Over 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).
    Original languageEnglish
    Title of host publicationIEEE Congress on Evolutionary Computation 2008
    Subtitle of host publicationCEC 2008
    PublisherInstitute of Electrical and Electronics Engineers (IEEE)
    Pages2498-2504
    Volume2008
    ISBN (Print)978-1-4244-1822-0
    DOIs
    Publication statusPublished - 2008
    EventIEEE Congress on Evolutionary Computation 2008 - Hong Kong, Hong Kong
    Duration: 1 Jun 20086 Jun 2008

    Conference

    ConferenceIEEE Congress on Evolutionary Computation 2008
    Country/TerritoryHong Kong
    CityHong Kong
    Period1/06/086/06/08

    Fingerprint

    Dive into the research topics of 'Combinatorial landscape analysis for k-SAT instances'. Together they form a unique fingerprint.

    Cite this