An improved local search algorithm for 3-SAT

DOI10.1016/J.ENDM.2004.03.021MaRDI QIDQ3439130zbMATH OpenOpenAlexFDO

Authors Tobias Brueggemann, Walter Kern

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://research.utwente.nl/en/publications/an-improved-local-search-algorithm-for-3sat(dd786856-36cb-40eb-806d-ca08c9d9f777).html

zbMATH Keywords

3-SATexact algorithmlocal search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Search theory (90B40)

Recommendations

• An improved deterministic local search algorithm for 3-SAT
• An efficient local search method for random 3-satisfiability
• Improving local search for random 3-SAT using quantitative configuration checking
• Improved randomized algorithms for 3-SAT
• Local search algorithms for SAT: an empirical evaluation
• Local search algorithms for SAT: an empirical evaluation
• Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
• scientific article; zbMATH DE number 2086385
• An efficient algorithm for the 3-satisfiability problem

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A probabilistic algorithm for k-SAT based on limited local search and restart
• scientific article; zbMATH DE number 2086385 (Why is no real title available?)

Cited in

(2)

• Guided Search and a Faster Deterministic Algorithm for 3-SAT
• An improvement of the algorithm of Hertli for the unique 3SAT problem

This page was built for publication: An improved local search algorithm for 3-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439130)