There are several approaches to attack hard problems. All have their merits but also their
limitations and need a large body of theory as their basis. A number of books for each one
exist: books on complexity theory others on approximation algorithms heuristic approaches
parametrized complexity and yet others on randomized algorithms. This book discusses
thoroughly all of the above approaches. And amazingly at the same time does this in a style
that makes the book accessible not only to theoreticians but also to the non-specialist to
the student or teacher and to the programmer. Do you think that mathematical rigor and
accessibility contradict? Look at this book to find out that they do not due to the admirable
talent of the author to present his material in a clear and concise way with the idea behind
the approach spelled out explicitly often with a revealing example. Reading this book is a
beautiful experience and I can highly recommend it to anyone interested in learning how to
solve hard problems. It is not just a condensed union of material from other books. Because it
discusses the different approaches in depth it has the chance to compare them in detail and
most importantly to highlight under what circumstances which approach might be worth
exploring. No book on a single type of solution can do that but this book does it in an
absolutely fascinating way that can serve as a pattern for theory textbooks with a high level
of generality. (Peter Widmayer) The second edition extends the part on the method of relaxation
to linear programming with an emphasis on rounding LP-duality and primal-dual schema and
provides a self-contained and transparent presentation of the design of randomized algorithms
for primality testing.
