Modelling the dynamics of stochastic local search on \(k\)-SAT

DOI10.1007/s10732-007-9023-5zbMath1142.90460OpenAlexW2009739012MaRDI QIDQ930153

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

Stochastic algorithmsAlgorithm analysisLocal searchExperimental evaluation

Mathematics Subject Classification ID

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

Uses Software

• SATLIB
• Tabu search

Cites Work

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

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