Local search methods based on variable focusing for random K-satisfiability
Loading...
Access rights
© 2015 American Physical Society (APS). This is the accepted version of the following article: Lemoy, Rémi & Alava, Mikko J. & Aurell, Erik. 2015. Local search methods based on variable focusing for random K-satisfiability. Physical Review E. Volume 91, Issue 1. 013305/1-6. ISSN 1539-3755 (printed). DOI: 10.1103/physreve.91.013305, which has been published in final form at http://journals.aps.org/pre/abstract/10.1103/PhysRevE.91.013305.
Final published version
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
013305/1-6
Series
Physical Review E, Volume 91, Issue 1
Abstract
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.Description
Other note
Citation
Lemoy, Rémi & Alava, Mikko J. & Aurell, Erik. 2015. Local search methods based on variable focusing for random K-satisfiability. Physical Review E. Volume 91, Issue 1. 013305/1-6. ISSN 1539-3755 (printed). DOI: 10.1103/physreve.91.013305.