Theoretical Aspects of Local Search (eBook)

Wil Michiels, Emile Aarts, Jan Korst (Autoren)

eBook Download: PDF

2007
VIII, 238 Seiten
Springer Berlin (Verlag)
9783540358541 (ISBN)

Infos

Local search has been applied successfully to a diverse collection of optimization problems. It`s appreciated for its basic conceptual foundation, its general applicability, and its power to serve as a source for new search paradigms. The typical characteristics of combinatorial optimization problems to which local search can be applied, its relation to complexity theory, and the combination with randomized search features have led to a wealth of interesting theoretical results. However, these results are scattered throughout the literature. This is the first book that presents a large collection of theoretical results in a consistent manner, thus providing the reader with a coherent overview of the achievements obtained so far, but also serving as a source of inspiration for the development of novel results in the challenging field of local search.

Inhalt

Preface 5
Contents 7
1 Introduction 9
2 Basic Examples 19
3 Indirect Solution Representations 47
4 Properties of Neighborhood Functions 61
5 Performance Guarantees 70
6 Time Complexity 103
7 Metaheuristics 141
8 Asymptotic Convergence of Simulated Annealing 154
A Graph Theory 191
B Complexity Theory and Approximation Algorithms 194
C PLS-Complete Problems 201
Bibliography 212
Author Index 222
Subject Index 226

Produkt-Details

• Erscheint lt. Verlag: 17.1.2007
• Reihe/Serie: Monographs in Theoretical Computer Science. An EATCS Series
• Reihe/Serie: Monographs in Theoretical Computer Science. An EATCS Series
• Zusatzinfo: VIII, 238 p. 70 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• Schlagworte: algorithm • Algorithm analysis and problem complexity • algorithms • Asymptotic convergence • combinatorial optimization • Complexity • Complexity theory • Graph • graph theory • Heuristics • Local Search • Metaheuristic • Optimization • performance guarantees • PLS-completeness • Polynomial-time local search (PLS) • SiM
• ISBN-13: 9783540358541 / 9783540358541