Reference : Local search methods based on variable focusing for random K-satisfiability
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Physics
http://hdl.handle.net/10993/31614
Local search methods based on variable focusing for random K-satisfiability
-
Lemoy, Rémi mailto [University of Luxembourg > Faculty of Language and Literature, Humanities, Arts and Education (FLSHASE) > Identités, Politiques, Sociétés, Espaces (IPSE)]
Alava, Mikko [Aalto Univ, Dept Appl Phys, Espoo, Finland.]
Aurell, Erik [Aalto Univ, Dept Informat & Comp Sci, Espoo, Finland.]
2015
PHYSICAL REVIEW E
Amer Physical Soc
91
1
013305-6
Yes (verified by ORBilu)
International
1539-3755
College Pk
[en] We introduce variable focused local search algorithms for satisfiabiliity problems. Usual approaches focus uniformly on unsatisfied clauses. The methods described here work by focusing on random variables in unsatisfied clauses. Variants are considered where variables are selected uniformly and randomly or by introducing a bias towards picking variables participating in several unsatistified clauses. These are studied in the case of the random 3-SAT problem, together with an alternative energy definition, the number of variables in unsatisfied constraints. The variable-based focused Metropolis search (V-FMS) is found to be quite close in performance to the standard clause-based FMS at optimal noise. At infinite noise, instead, the threshold for the linearity of solution times with instance size is improved by picking preferably variables in several UNSAT clauses. Consequences for algorithmic design are discussed.
Center of Excellence program of the Academy of Finland ; Academy of Finland Distinguished Professor program
http://hdl.handle.net/10993/31614
10.1103/PhysRevE.91.013305
The authors thank A. Mozeika and S. Seitz for discussions about variable focusing. Professor P. Orponen (Aalto) is acknowledged for discussions. This work was supported by funding from the Center of Excellence program of the Academy of Finland, for the COIN and COMP Centers, as well as the Academy of Finland Distinguished Professor program (E.A.). We acknowledge the computational resources provided by the Aalto Science-IT project.

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
Lemoy_Alava_Aurell_PhysRevE_2015.91.013305.pdfPublisher postprint944.9 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.