Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Local search methods based on variable focusing for random K-satisfiability
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
2015 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 91, no 1, 013305- p.Article in journal (Refereed) Published
Abstract [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.

Place, publisher, year, edition, pages
2015. Vol. 91, no 1, 013305- p.
National Category
Condensed Matter Physics
Identifiers
URN: urn:nbn:se:kth:diva-160390DOI: 10.1103/PhysRevE.91.013305ISI: 000348159600007Scopus ID: 2-s2.0-84921778549OAI: oai:DiVA.org:kth-160390DiVA: diva2:790876
Note

QC 20150226

Available from: 2015-02-26 Created: 2015-02-19 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Aurell, Erik
By organisation
Computational Biology, CBACCESS Linnaeus Centre
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics
Condensed Matter Physics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 60 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf