Theoretical Aspects of Local Search (Monographs in Theoretical...

Features

• Cover Type: Hard Cover with 238 pages
• Published by: Springer
• Edition: 1st Edition February 2, 2007
• Written in: English
• ISBN 10 Number: 3540358536
• ISBN 13 Number: 978-3540358534
• Book Dimensions: 9.3 x 6.1 x 0.7 inches
• Weighs: 1.2 pounds

Product Description


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.

Reader Reviews
The authors survey a bunch of classic and important problems in computation. Travelling salesman, machine scheduling and graph colours amongst others. There have been decades of research into these. Certainly, earlier texts have also arisen, that attempt to summarise this research. Perhaps the attraction of this book is its recent vintage. It goes into the main methods used. Like simulated annealing, and the Metropolis Monte Carlo algorithm. There are theories of how to estimate the computational complexity of the methods. Measured as a function of the problem size. With a key idea being how to efficiently search a "small" neighbourhood of a parameter space. Since it is impractical to exhaustively search all possible values, even if this is finite. The book is certainly very theoretical. But lest you think the problems are abstract, there is one which is increasingly germane in the computing world. Multiprocessor scheduling. Especially since clock speeds are maxing out, due to excessive power consumption amongst other factors. So the other way to improve performance is to migrate to multicores. Now, this might not appear at first to be exactly the multiprocessor scheduling problem. But in fact it is. The issue of how to efficiently use a bunch of cores in the same processor is fundamentally no different.