An Empirical Analysis of Search in GSAT

I. P. Gent, T. Walsh

We describe an extensive study of search in GSAT, an approximation procedure for propositional satisfiability. GSAT performs greedy hill-climbing on the number of satisfied clauses…