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).
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 language | English |
|---|---|
| Title of host publication | IEEE Congress on Evolutionary Computation 2008 |
| Subtitle of host publication | CEC 2008 |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| Pages | 2498-2504 |
| Volume | 2008 |
| ISBN (Print) | 978-1-4244-1822-0 |
| DOIs | |
| Publication status | Published - 2008 |
| Event | IEEE Congress on Evolutionary Computation 2008 - Hong Kong, Hong Kong Duration: 1 Jun 2008 → 6 Jun 2008 |
Conference
| Conference | IEEE Congress on Evolutionary Computation 2008 |
|---|---|
| Country/Territory | Hong Kong |
| City | Hong Kong |
| Period | 1/06/08 → 6/06/08 |