Modelling the dynamics of stochastic local search on k-SAT

DOI10.1007/S10732-007-9023-5zbMATH Open1142.90460OpenAlexW2009739012MaRDI QIDQ930153FDOQ930153

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Analysis of local search landscapes for \(k\)-SAT instances
• 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
• Title not available (Why is that?)

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)