Reference:
Sakari Seitz, Mikko Alava, and Pekka Orponen. Focused local search for random 3satisfiability. Journal of Statistical Mechanics: Theory and Experiment, P06006:1–27, June 2005.
Abstract:
A local search algorithm solving an NPcomplete optimisation problem can be viewed as a stochastic process moving in an 'energy landscape' towards eventually finding an optimal solution. For the random 3satisfiability problem, the heuristic of em focusing the local moves on the presently unsatisfied clauses is known to be very effective: the time to solution has been observed to grow only linearly in the number of variables, for a given clausestovariables ratio sufficiently far below the critical satisfiability threshold . We present numerical results on the behaviour of three focused local search algorithms for this problem, considering in particular the characteristics of a focused variant of simple Metropolis dynamics. We estimate the optimal value for the ``temperature'' parameter for this algorithm, such that its lineartime regime extends as close to as possible. Similar parameter optimisation is performed also for the wellknown WalkSAT algorithm and for the less studied, but very well performing Focused RecordtoRecord Travel method. We observe that with an appropriate choice of parameters, the linear time regime for each of these algorithms seems to extend well into ratios — much further than has so far been generally assumed. We discuss the statistics of solution times for the algorithms, relate their performance to the process of ``whitening'', and present some conjectures on the shape of their computational phase diagrams.
Keywords:
satisfiability, local search, phase transition, WalkSAT, Metropolis algorithm, Record to Record Travel
Suggested BibTeX entry:
@article{SeAO05b,
author = {Sakari Seitz and Mikko Alava and Pekka Orponen},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
month = {June},
pages = {127},
title = {Focused local search for random 3satisfiability},
volume = {P06006},
year = {2005},
}
