Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/75348
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | A theoretical analysis of the k-satisfiability search space |
Author: | Sutton, Andrew M. Howe, Adele E. Whitley, L. Darrell |
Citation: | Lecture Notes in Computer Science, 2009; 5752:46-60 |
Publisher: | Springer-Verlag Berlin |
Issue Date: | 2009 |
ISBN: | 9783642037511 |
ISSN: | 0302-9743 |
School/Discipline: | School of Computer Science |
Statement of Responsibility: | Andrew M. Sutton, Adele E. Howe, and L. Darrell Whitley |
Abstract: | Local search algorithms perform surprisingly well on the k-satisfiability (k-SAT) problem. However, few theoretical analyses of the k-SAT search space exist. In this paper we study the search space of the k-SAT problem and show that it can be analyzed by a decomposition. In particular, we prove that the objective function can be represented as a superposition of exactly k elementary landscapes. We show that this decomposition allows us to immediately compute the expectation of the objective function evaluated across neighboring points. We use this result to prove previously unknown bounds for local maxima and plateau width in the 3-SAT search space. We compute these bounds numerically for a number of instances and show that they are non-trivial across a large set of benchmarks. |
Description: | Also published as a book chapter: Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, 2009 / Stützle, Thomas; Birattari, Mauro; Hoos, Holger H. (eds.), pp.46-60 |
Rights: | © Springer-Verlag Berlin Heidelberg 2009 |
DOI: | 10.1007/978-3-642-03751-1_4 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.