SAT: references on satisfiability
Local search methods
GSAT
A New Method for Solving Hard Satisfiability Problems
Bart Selman, Hector Levesque and David Mitchell,
Proceedings AAAI-92.
An Empirical Analysis of Search in GSAT.
Ian Gent and Toby Walsh,
Journal of Artificial Intelligence Research,
Vol. 1, September 1993.
GenSAT (including HSAT)
Towards an Understanding of Hill-climbing Procedures for SAT
Ian Gent and Toby Walsh.
Proceedings of AAAI-93.
Weights
An Empirical Study of Greedy Local Search for Satisfiability Testing
Bart Selman and Henry Kautz,
Proc. AAAI-93.
Weighting for Godot: Learning heuristics for
GSAT
J. Frank, Proc. AAAI-96.
Random Walk
Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems
Bart Selman and Henry Kautz,
Proc. IJCAI-93.
Unsatisfied Variables in Local Search
Ian Gent and Toby Walsh.
in `Hybrid Problems, Hybrid Solutions', ed. J. Hallam, IOS Press, Amsterdam,
1995, pages 73-85.
(Proceedings of AISB-95.)
WalkSAT
Local Search Strategies for Satisfiability Testing
Bart Selman, Henry Kautz and Bram Cohen, Proceedings
of 2nd DIMACS Challenge on Cliques, Coloring and Satisfiability.
Novelty
Evidence for Invariants in Local Search
David McAllester,
Bart Selman,
and
Henry Kautz.
Proc. AAAI-97, Providence, RI, 1997.
The greedy algorithm
On the Stupid Algorithm for Satisfiability
Ian Gent. Technical report, APES-03-1998, April 1998.