Local search characteristics of incomplete SAT procedures

DOI10.1016/S0004-3702(01)00151-5MaRDI QIDQ5958635zbMATH OpenFDO

Authors D. Schuurmans, F. Southey

Publication date 3 March 2002

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0004-3702(01)00151-5

zbMATH Keywords

constraint satisfactionexperimental analysislocal searchsatisfiability

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 956863
• scientific article; zbMATH DE number 5510694
• Local search algorithms for SAT: an empirical evaluation
• SAT local search algorithms: Worst-case study
• SAT local search algorithms: Worst-case study

Cites work

• A discrete Lagrangian-based global-search method for solving satisfiability problems
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• scientific article; zbMATH DE number 1237740 (Why is no real title available?)
• scientific article; zbMATH DE number 1149403 (Why is no real title available?)
• Local search characteristics of incomplete SAT procedures

Cited in

(23)

• Graph coloring by multiagent fusion search
• Boosting complete techniques thanks to local search methods
• Constraint-directed search for all-interval series
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
• Understanding the role of noise in stochastic local search: analysis and experiments
• Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks
• Constraint partitioning in penalty formulations for solving temporal planning problems
• The state of SAT
• Local search algorithms for SAT: an empirical evaluation
• SAT local search algorithms: Worst-case study
• Local search to approximate MAX NAE-k-SAT tightly
• A decision procedure for probability calculus with applications
• Variable Dependency in Local Search: Prevention Is Better Than Cure
• Approximate coherence-based reasoning
• Improved local search for circuit satisfiability
• Approximating Max NAE-\(k\)-SAT by anonymous local search
• Another Complete Local Search Method for SAT
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• Theory and Applications of Satisfiability Testing
• Local search characteristics of incomplete SAT procedures
• Analysis of local search landscapes for \(k\)-SAT instances
• Clause weighting local search for SAT
• The island confinement method for reducing search space in local search methods

This page was built for publication: Local search characteristics of incomplete SAT procedures

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