Improving configuration checking for satisfiable random k-SAT instances

DOI10.1007/S10472-016-9515-9MaRDI QIDQ513324zbMATH OpenOpenAlexFDO

Authors André Abramé, Djamal Habet, Donia Toumi

Publication date 6 March 2017

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-016-9515-9

zbMATH Keywords

configuration checkinglocal searchnovelty heuristicrandom \(k\)-SAT

Mathematics Subject Classification ID

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

Recommendations

• Local search for Boolean satisfiability with configuration checking and subscore
• Improving local search for random 3-SAT using quantitative configuration checking
• CCAnr: a configuration checking based local search solver for non-random satisfiability
• scientific article; zbMATH DE number 956863
• An efficient local search method for random 3-satisfiability

Cites work

• A machine program for theorem-proving
• GRASP: a search algorithm for propositional satisfiability
• scientific article; zbMATH DE number 5510694 (Why is no real title available?)
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Improving stochastic local search for SAT with a new probability distribution
• Local search for Boolean satisfiability with configuration checking and subscore
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(15)

• An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem
• Automated non-monotonic reasoning in System \textbf{P}
• Using the method of conditional expectations to supply an improved starting point for CCLS
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• An improved configuration checking-based algorithm for the unicost set covering problem
• Local search for diversified top-\(k\) clique search problem
• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• CCAnr: a configuration checking based local search solver for non-random satisfiability
• Improving local search for random 3-SAT using quantitative configuration checking
• Local search for Boolean satisfiability with configuration checking and subscore
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• Verifiable Obtained Random Subsets for Improving SPHINCS+

Describes a project that uses

Uses Software

• CCASat
• MiniSat

This page was built for publication: Improving configuration checking for satisfiable random \(k\)-SAT instances

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