The probabilistic analysis of a greedy satisfiability algorithm

DOI10.1002/RSA.20104MaRDI QIDQ5486323zbMATH OpenOpenAlexFDO

Authors A. C. Kaporis, L. M. Kirousis, Efthimios G. Lalas

Publication date 6 September 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20104

Mathematics Subject Classification ID

Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1947423
• On the greedy algorithm for satisfiability
• scientific article; zbMATH DE number 437557
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Probabilistic performance of a heurisic for the satisfiability problem

Cites work

• A Computing Procedure for Quantification Theory
• A sharp threshold in proof complexity
• Almost all graphs with average degree 4 are 3-colorable
• Hard examples for resolution
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 1246231 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1142298 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• scientific article; zbMATH DE number 2119678 (Why is no real title available?)
• Many hard examples for resolution
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The unsatisfiability threshold revisited

Cited in

(30)

• When does the giant component bring unsatisfiability?
• Probabilistic performance of a heurisic for the satisfiability problem
• On the lower bounds of random Max 3 and 4-SAT
• Stochastic analysis of greedy algorithms for the subset sum problem
• A model of random industrial SAT
• On the satisfiability threshold of formulas with three literals per clause
• Super solutions of random \((3 + p)\)-SAT
• An algorithm for random signed 3-SAT with intervals
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• A probabilistic study on the satisfiability problem
• A Probabilistic Analysis of Christofides’ Algorithm
• scientific article; zbMATH DE number 3909744 (Why is no real title available?)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• scientific article; zbMATH DE number 4057284 (Why is no real title available?)
• scientific article; zbMATH DE number 4102824 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• The cook-book approach to the differential equation method
• Average Performance of Heuristics for Satisfiability
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Branching process approach for 2-SAT thresholds
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• The satisfiability threshold for non-uniform random 2-SAT
• Bounds on the satisfiability threshold for power law distributed random SAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• A randomized algorithm for 3-SAT
• Sufficient condition for polynomial solvability of random 3-CNF formulas
• Title not available (Why is no real title available?)
• An improved generator for 3-CNF formulas
• An upper (lower) bound for Max (Min) CSP
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas

This page was built for publication: The probabilistic analysis of a greedy satisfiability algorithm

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