E. Koutsoupias and C. H. Papadimitriou.
On the greedy algorithm for satisfiability.
Information Processing Letters, 43(1):53--55, August 1992.
Abstract
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.Bib
@string{ipl= {Information Processing Letters}}
@Article{KP92,
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}
}