Focused local search for random 3-satisfiability (2005)
AUTHORS:
Seitz Sakari,
Alava Mikko,
Orponen Pekka
JOURNAL:
Journal of Statistical Mechanics: Theory and Experiment
VOLUME:
P06006
PAGES:
1--27
URL:
http://dx.doi.org/10.1088/1742-5468/2005/06/P06006
@article{ SeAO05b, author = "Seitz, Sakari and Alava, Mikko and Orponen, Pekka", note = "", title = "Focused local search for random 3-satisfiability", url = "http://dx.doi.org/10.1088/1742-5468/2005/06/P06006", journal = "Journal of Statistical Mechanics: Theory and Experiment", number = "", abstract = "A local search algorithm solving an NP-complete optimisation problem can be viewed as a stochastic process moving in an 'energy landscape' towards eventually finding an optimal solution. For the random 3-satisfiability 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 clauses-to-variables ratio $\alpha$ sufficiently far below the critical satisfiability threshold $\alpha_c \approx 4.27$. 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 $\eta$ for this algorithm, such that its linear-time regime extends as close to $\alpha_c$ as possible. Similar parameter optimisation is performed also for the well-known WalkSAT algorithm and for the less studied, but very well performing Focused Record-to-Record 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 $\alpha > 4.2$ --- 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.", month = "June", volume = "P06006", flags = "public", year = "2005", keywords = "satisfiability, local search, phase transition, WalkSAT, Metropolis algorithm, Record to Record Travel", pages = "1--27" }