Analysis of random noise and random walk algorithms for satisfiability testing

DOI10.1007/3-540-45349-0_21MaRDI QIDQ4473032zbMATH OpenFDO

Authors Bhaskar Krishnamachari, Xi Xie, Stephen B. Wicker, Bart Selman

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1894/18940278.htm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Probabilistic analysis of satisfiability algorithms
• A comparative runtime analysis of heuristic algorithms for satisfiability problems
• Local search algorithms for SAT: an empirical evaluation
• An empirical study of optimal noise and runtime distributions in local search
• Stochastic systematic search algorithms for satisfiability

Cited in

(2)

• The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems
• A comparative runtime analysis of heuristic algorithms for satisfiability problems

Describes a project that uses

Uses Software

• Walksat

This page was built for publication: Analysis of random noise and random walk algorithms for satisfiability testing

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