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.
Contents
1- Introduction
2- Elementary Fundamentals
- Introduction
- Fundamentals of Mathematicals
- Fundamentals of Algorithms
3- Deterministic Approaches
- Introduction
- Pseudo-Polynomial-Time Algorithms
- Parameterized Complexity
- Branch-and-Bound
- Lowering Worst Case Complexity of Exponential
Algorithms
- Local Search
- Relaxation to Linear Programming
- Bibliographical Remarks
4- Approximation Algorithms
- Introduction
- Fundamentals
- Algorithm Design
- Inapproximability
- Bibliographical Remarks
5- Randomized Algorithms
Introduction
- Classification and Randomized Algorithms and Design
Paradigms
- Design of Randomized Algorithms
- Derandomization
- Bibliographical Remarks
6- Heuristics
- Introduction
- Simulated Annealing
- Genetic Algorithms
- Bibliographical Remarks
7- A Guide to Solving Hard Problems
- Introduction
- Taking over an Algorithm Task or a few Words about
Money
- Combining Different Concepts and Techniques
- Comparing Different Approaches
- Speedup by Parallelization
- New Technologies
- Glossary of Basic Terms