The probabilistic analysis of a greedy satisfiability algorithm

Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas

Research output: Contribution to journalArticlepeer-review


On input a random 3-CNF formula of clauses-to-variables ratio r3 applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r3 < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r3 < 3.26. We improve up to r3 < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.

Original languageEnglish (US)
Pages (from-to)444-480
Number of pages37
JournalRandom Structures and Algorithms
Issue number4
StatePublished - Jul 2006

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'The probabilistic analysis of a greedy satisfiability algorithm'. Together they form a unique fingerprint.

Cite this