Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

E. Koutsoupias and C. H. Papadimitriou. On the greedy algorithm for satisfiability. Information Processing Letters, 43(1):53--55, August 1992.
Download: pdf ps


We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment, and repeatedly flips the variable that improves the number of satisfied clauses the most, almost always succeeds in discovering a satisfying truth assignment.


@string{ipl= {Information Processing Letters}}

  author =       {E. Koutsoupias  and  C. H. Papadimitriou},
  title =        {On the greedy algorithm for satisfiability},
  journal =      ipl,
  year =         1992,
  month =        aug,
  volume =       43,
  number =       1,
  pages =        {53--55}