A comparative runtime analysis of heuristic algorithms for satisfiability problems

DOI10.1016/J.ARTINT.2008.11.002MaRDI QIDQ835804zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yuren Zhou, Jun He, 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

random walkhybrid algorithmheuristic algorithmsruntime analysisBoolean satisfiabilityexpected first hitting time(1+1) EA

Mathematics Subject Classification ID

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

Recommendations

• Stochastic Algorithms: Foundations and Applications
• Probabilistic analysis of satisfiability algorithms
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• scientific article; zbMATH DE number 4102824
• scientific article; zbMATH DE number 2080313

Cites work

• scientific article; zbMATH DE number 3680816 (Why is no real title available?)
• scientific article; zbMATH DE number 41891 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 2243370 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• An improved exponential-time algorithm for k -SAT
• Implementing the Davis-Putnam method
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Modeling genetic algorithms with Markov chains.
• On the analysis of the \((1+1)\) evolutionary algorithm
• Optimization by simulated annealing
• Principles of Stochastic Local Search
• Probability Inequalities for Sums of Bounded Random Variables
• Survey propagation: An algorithm for satisfiability
• The complexity of theorem-proving procedures
• Towards an analytic framework for analysing the computation time of evolutionary algorithms
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination

Cited in

(9)

• scientific article; zbMATH DE number 2080313 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• scientific article; zbMATH DE number 6519724 (Why is no real title available?)
• The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems
• Computational Science and Its Applications – ICCSA 2004
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• scientific article; zbMATH DE number 1765679 (Why is no real title available?)
• scientific article; zbMATH DE number 2188496 (Why is no real title available?)
• A comparative performance analysis of evolutionary algorithms on k-median and facility location problems

Describes a project that uses

Uses Software

• UnitWalk

This page was built for publication: A comparative runtime analysis of heuristic algorithms for satisfiability problems

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