Short Review of the Book
Algorithms for Hard Problems
by
Juraj Hromkovic
The definition of the class of computational problems for which a claimed solution can be verified in polynomial time has been a major step in the development of Theoretical Computer Science. In the seventies, numerous practically important problems have been found to be hardest in that class, and it is the general belief today that no efficient algorithm for their solution will be found. If a practical problem cannot be solved rapidly, what should one do? For optimization problems, solutions that are close to optimal might still be good enough in many cases. A decade ago, in another major step in the theory of computation, a whole theory was developed of how closely one can approximate optimal solutions. The amazing connection to probabilistically checkable proofs revealed a "law of nature" for what we cannot hope to achieve: There are important problems for which no good approximation can be found efficiently. So, what to do then? We might just try some clever approach and hope that a good solution will result for many relevant inputs. Methods of this sort are called heuristics. Or one might make random choices every now and then, and hope to avoid systematically bad decisions for any input that way. Or one might limit the set of inputs in a certain way, expressed by some important problem parameter. Since these different approaches have their merits, but also their limitations, and need quite a body of theory as their basis, a number of books for each one exist: In a theorists bookshelf, you will find a book on NP-hardness and complexity theory, another on approximation algorithms, another on heuristic appraches, another on parameterized complexity, and yet another on randomized algorithms. Which one do you pick if you need to solve a problem? Pick the book on "Algorithms for Hard Problems" by Juraj Hromkovic. This book discusses thoroughly, from a theoretical perspective, all of the above approaches. And, amazingly, at the same time does this in a style that makes the book accessible to the non-specialist, to the Computer Science student or teacher, and to the programmer. You think that mathematical rigor and accessibility contradict? Look at the book to find out that it doesn't, due to an admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out first explicitly, often with a revealing example. Aha. It is a beautiful experience to read the book; you can feel on every page the author's own professional involvement in developing the theory of computation. The fascination of the author with the field, and with his own contributions of course, make the book a gem. I can highly recommend it to anyone interested in learning how to solve hard computational problems. It is not just a condensed union of material in other books: Because it discussed the different approaches in depth, it has the chance to relate and compare them in depth, and to highlight under what circumstances which approach might be worthwile exploring. No book on a single type of solution can do that, but the book by Juraj Hromkovic does it. In an absolutely fascinating way that can serve as a pattern for theory textbooks in high generality.
Zurich, January 25, 2002 Peter Widmayer
