Division of Informatics
Forrest Hill & 80 South Bridge
Research Paper #614 | |
|---|---|
| Title: | Towards an Understanding of Hill-Climbing Procedures for Sat |
| Authors: | Gent,I; Walsh,T |
| Date: | 1993 |
| Presented: | Submitted to AAAI-93 |
| Keywords: | |
| Abstract: | Recently several local hill-climbing procedures for propositional satisfiability have been proposed, which are able to solve large and difficult problems beyond the reach of conventional algorithms like Davis-Putnam. By the introduction of some new variants of these procedures, we provide strong experimental evidence to support the conjecture that neither greediness nor randomness is important in these procedures. One of the variants introduced seems to offer significant improvements over earlier procedures. in addition, we investigate experimentally how their performance depends on their parameters. Our results suggest that run-time scales less than simply exponentially in the problem size. |
| Download: | POSTSCRIPT COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}