Modelling the dynamics of stochastic local search on k-SAT

DOI10.1007/S10732-007-9023-5MaRDI QIDQ930153zbMATHOpenAlexFDO

Authors Nicolas G. Fournier

Publication date 23 June 2008

Published in Journal of Heuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10732-007-9023-5

zbMATH Keywords

Algorithm analysisLocal searchExperimental evaluationStochastic algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Stochastic programming (90C15)

Recommendations

• scientific article; zbMATH DE number 2086447
• Analysis of local search landscapes for \(k\)-SAT instances
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A Theoretical Analysis of Search in GSAT
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart

Cites work

• scientific article; zbMATH DE number 1381974 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3543391 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1149403 (Why is no real title available?)
• scientific article; zbMATH DE number 2086385 (Why is no real title available?)
• scientific article; zbMATH DE number 1860684 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Algorithms for the maximum satisfiability problem
• An improved deterministic local search algorithm for 3-SAT
• Bandwidth Packing: A Tabu Search Approach
• Convergence of an annealing algorithm
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Evolutionary computation
• Future paths for integer programming and links to artificial intelligence
• Local search algorithms for SAT: an empirical evaluation
• Monte Carlo sampling methods using Markov chains and their applications
• Some optimal inapproximability results
• The time complexity of maximum matching by simulated annealing

Cited in

(6)

• Analysis of local search landscapes for \(k\)-SAT instances
• scientific article; zbMATH DE number 2086447 (Why is no real title available?)
• Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Stochastic systematic search algorithms for satisfiability
• scientific article; zbMATH DE number 2226659 (Why is no real title available?)

Describes a project that uses

Uses Software

• SATLIB
• Tabu search

This page was built for publication: Modelling the dynamics of stochastic local search on \(k\)-SAT

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