research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Publication

Type of publication:Inproceedings
Entered by:
TitleHow to Tell a Good Neighborhood from a Bad One: Satisfiability of Boolean Formulas
Bibtex cite IDRACTI-RU1-2004-14
Booktitle 3rd Workshop on Efficient (WEA 2004)
Year published 2004
Month May
Pages 199-212
Publisher Springer Berlin / Heidelberg
URL http://wea2004.inf.puc-rio.br/
DOI 10.1007/b97914
Abstract
One of the major problems algorithm designers usually face is to know in advance whether a proposed optimization algorithm is going to behave as planned, and if not, what changes are to be made to the way new solutions are examined so that the algorithm performs nicely. In this work we develop a methodology for differentiating good neighborhoods from bad ones. As a case study we consider the structure of the space of assignments for random 3-SAT formulas and we compare two neighborhoods, a simple and a more refined one that we already know the corresponding algorithm behaves extremely well. We give evidence that it is possible to tell in advance what neighborhood structure will give rise to a good search algorithm and we show how our methodology could have been used to discover some recent results on the structure of the SAT space of solutions. We use as a tool Go with the winners, an optimization heuristic that uses many particles that independently search the space of all possible solutions. By gathering statistics, we compare the combinatorial characteristics of the different neighborhoods and we show that there are certain features that make a neighborhood better than another, thus giving rise to good search algorithms.
Authors
Dimitriou, Tassos
Spirakis, Paul
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
fulltext.pdf (main file)
fulltext.pdf
 
Publication ID220