Local search algorithms for SAT: Worst-case analysis

DOI10.1007/BFB0054372MaRDI QIDQ5054860zbMATH OpenOpenAlexFDO

Authors Edward A. Hirsch

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0054372

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40)

Recommendations

• SAT local search algorithms: Worst-case study
• SAT local search algorithms: Worst-case study
• Local search algorithms for SAT: an empirical evaluation
• Local search algorithms for SAT: an empirical evaluation
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

Cites work

• Average case results for satisfiability algorithms under the random-clause-width model
• scientific article; zbMATH DE number 3952007 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303594 (Why is no real title available?)
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• On the greedy algorithm for satisfiability
• Solving satisfiability in less than \(2^ n\) steps

Cited in

(11)

• Worst-case study of local search for MAX-\(k\)-SAT.
• Local search algorithms for SAT: an empirical evaluation
• SAT local search algorithms: Worst-case study
• Local search algorithms for SAT: an empirical evaluation
• SAT local search algorithms: Worst-case study
• scientific article; zbMATH DE number 1341458 (Why is no real title available?)
• scientific article; zbMATH DE number 1467488 (Why is no real title available?)
• scientific article; zbMATH DE number 1834642 (Why is no real title available?)
• Improved local search for circuit satisfiability
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• Local Search for Unsatisfiability

This page was built for publication: Local search algorithms for SAT: Worst-case analysis

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