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.

Скачать книгу бесплатно (pdf, 2.46 Mb)

---

Читать «Theoretical Aspects of Local Search (Monographs in Theoretical Computer Science. An EATCS Series)»