The probabilistic analysis of a greedy satisfiability algorithm

DOI10.1002/RSA.20104zbMATH Open1099.68100OpenAlexW2602510746MaRDI QIDQ5486323FDOQ5486323

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

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

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

Mathematics Subject Classification ID

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

Cites Work

• Hard examples for resolution
• Title not available (Why is that?)
• A Computing Procedure for Quantification Theory
• Many hard examples for resolution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A sharp threshold in proof complexity
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Title not available (Why is that?)
• The unsatisfiability threshold revisited
• Almost all graphs with average degree 4 are 3-colorable

Cited In (27)

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

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)