Theoretical aspects of local search

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.

1 Introduction	p. 1
1.1 Basics of Local Search	p. 3
1.2 Outline of the Book	p. 9
1.3 Bibliographical Notes	p. 9
1.4 Exercises	p. 10
2 Basic Examples	p. 11
2.1 Traveling Salesman Problem	p. 11
2.2 Machine Scheduling	p. 19
2.3 Steiner Tree Problem in Graphs	p. 23
2.4 Graph Coloring	p. 25
2.5 Uniform Graph Partitioning	p. 28
2.6 Stable Configuration in Hopfield Networks	p. 33
2.7 Bibliographical Notes	p. 34
2.8 Exercises	p. 36
3 Indirect Solution Representations	p. 39
3.1 Sum of Weighted Completion Time on Unrelated Machines	p. 40
3.2 Symmetric Earliness and Tardiness on a Single Machine	p. 41
3.3 Job Shop Scheduling	p. 45
3.4 Bibliographical Notes	p. 49
3.5 Exercises	p. 51
4 Properties of Neighborhood Functions	p. 53
4.1 Traveling Salesman Problem	p. 53
4.2 Job Shop Scheduling	p. 58
4.3 Bibliographical Notes	p. 60
4.4 Exercises	p. 60
5 Performance Guarantees	p. 63
5.1 Exact Neighborhood Functions	p. 64
5.2 Performance Ratios of Neighborhood Functions	p. 71
5.3 Non-Approximability Results	p. 79
5.4 From Neighborhood Function to Polynomial-Time Algorithm	p. 83
5.5 Bibliographical Notes	p. 89
5.6 Exercises	p. 91
6 Time Complexity	p. 97
6.1 Computational Complexity of Local Search Problems	p. 98
6.2 Time Complexity of Iterative Improvement	p. 120
6.3 Bibliographical Notes	p. 131
6.4 Exercises	p. 133
7 Metaheuristics	p. 135
7.1 Simulated Annealing	p. 136
7.2 Tabu Search	p. 139
7.3 Random Restart, GRASP, and Iterated Local Search	p. 141
7.4 Genetic Local Search	p. 142
7.5 Bibliographical Notes	p. 145
7.6 Exercises	p. 146
8 Asymptotic Convergence of Simulated Annealing	p. 149
8.1 Mathematical Modeling	p. 150
8.2 Stationary Distribution	p. 154
8.3 Homogeneous Markov Chains	p. 158
8.4 Equilibrium Statistics	p. 168
8.5 Inhomogeneous Markov Chains	p. 170
8.6 Non-Convergence Result for Tabu Search	p. 180
8.7 Bibliographical Notes	p. 181
8.8 Exercises	p. 183
A Graph Theory	p. 187
B Complexity Theory and Approximation Algorithms	p. 191
C PLS-Complete Problems	p. 199
Bibliography	p. 211
Author Index	p. 221
Subject Index	p. 225

Available:*

On Order

Summary

Summary

Table of Contents