A comparative runtime analysis of heuristic algorithms for satisfiability problems

DOI10.1016/j.artint.2008.11.002zbMath1192.68655OpenAlexW2005679383WikidataQ37415389 ScholiaQ37415389MaRDI QIDQ835804

Jun He, Yuren Zhou, Qing Nie

Publication date: 31 August 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: http://europepmc.org/articles/pmc2774825

zbMATH Keywords

heuristic algorithmsrandom walkBoolean satisfiabilityhybrid algorithmruntime analysisexpected first hitting time(1+1) EA

Mathematics Subject Classification ID

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

Related Items

A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems, On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem, A Computing Procedure for Quantification Theory, The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems

Uses Software

• UnitWalk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Towards an analytic framework for analysing the computation time of evolutionary algorithms
• Modeling genetic algorithms with Markov chains.
• On the analysis of the \((1+1)\) evolutionary algorithm
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
• Implementing the Davis-Putnam method
• An improved exponential-time algorithm for k -SAT
• Principles of Stochastic Local Search
• Survey propagation: An algorithm for satisfiability
• Probability Inequalities for Sums of Bounded Random Variables
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures