A comparative runtime analysis of heuristic algorithms for satisfiability problems

DOI10.1016/J.ARTINT.2008.11.002zbMATH Open1192.68655DBLPjournals/ai/ZhouHN09OpenAlexW2005679383WikidataQ37415389 ScholiaQ37415389MaRDI QIDQ835804FDOQ835804

Qing Nie, Jun He, Yuren Zhou

Publication date: 31 August 2009

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

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

Recommendations

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

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)

Cites Work

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

Cited In (9)

• On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem
• Title not available (Why is that?)
• A Computing Procedure for Quantification Theory
• Title not available (Why is that?)
• The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems
• Computational Science and Its Applications – ICCSA 2004
• Title not available (Why is that?)
• Title not available (Why is that?)
• A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems

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)