| Support Mail | | Help Index |
| | | | |
| References: 0 | Reference Citations: 0 | Review Citations: 0 |
The key idea is to consider optimisation problems---e.g., maximise some utility function subject to certain constraints---in their natural state, rather than to force them into the decision-problem framework of the theory of NP-completeness. Then one can study the closeness with which a polynomial-time algorithm is able to approximate the optimum solution as a measure of the problem's "approximability". The ratio of the solution actually produced to the optimal solution is the approximation ratio; it transpires that for some problems the approximation ratio can be arbitrarily close to $1$, for others it is strictly between $0$ and $1$, and for others still it is a function of $n$ tending to $0$ at a certain rate. (All this is assuming a maximisation problem.) Clearly there are two complementary activities here: finding efficient algorithms with good approximation ratios, and proving bounds on how good the approximation ratio may be, under some reasonable complexity-theoretic assumption such as $\rm P\not=NP$. Both of these activities have been vigorously pursued in recent years.
The book under review concentrates on the more optimistic of these activities, namely the design and analysis of efficient approximation algorithms with good performance guarantees. It is possibly the first textbook to provide an extensive and systematic coverage of this topic, though mention should be made of two existing publications: \ref[ Approximation algorithms for {\rm NP-hard problems}, PWS, Boston, 1997], a collection of survey articles, which achieves greater scope while assuming greater prior knowledge, and \ref[G. Ausiello et al., Complexity and approximation, Springer, Berlin, 1999; MR 2001f:68002], which has a broader complexity-theoretic feel.
The prerequisites for Vazirani's book are a grounding in the design and analysis of algorithms, and at least a passing acquaintance with the theory of NP-completeness. The book starts briskly, using simple examples to illustrate some of the key concepts and draw the reader rapidly in. The author avoids the temptation to overformalise or oversystemise the methods, preferring instead to insinuate them into the reader's mind through a sequence of case studies. Key concepts are introduced as required, so that the reader is not expected to plough through a morass of preliminary technical material. Copious exercises are included to test and deepen the reader's understanding. The book is based on courses given over a number of years, so one may assume that it is well proven in the field.
The first of the three parts of the book is on strictly combinatorial algorithms for optimisation problems. Much of this part of the book uses minimal mathematical raw material, and would be ideal for inspiring a student from a computer science background. The importance of obtaining good upper bounds (assuming a maximisation problem) on the optimal solution is emphasised. We learn that widely different levels of approximability may be exhibited by actual optimisation problems: within a factor arbitrarily close to 1 (e.g., the Euclidean travelling salesman problem), within some constant factor bounded away from 1 (e.g., the vertex cover problem), or within a logarithmic factor (e.g., the set cover problem).
The second part, on algorithms based on mathematical programming techniques, opens with an excellent introduction to linear programming duality, which is key to understanding many of the algorithms. The clarity of this introduction is a significant point in the book's favour. The set cover problem is used as a case study to investigate different ways to apply mathematical programming in the context of combinatorial optimisation problems. More recent algorithms based on semidefinite programming are treated in the closing chapter.
The third and final part is a sampler for topics slightly away from the primary concerns of the book. The shortest vector (in a geometric lattice) is here because the methods used have a particular flavour; counting problems because what is being approximated has an essentially different nature; and hardness of approximation because it is complementary to the main thrust of the book, which is the study of efficient algorithms. The negative results described in the last of these chapters are based on the theory of probabilistically checkable proofs, which is one of the greatest intellectual achievements of computational complexity theory. Really, this deserves a book to itself, so the author is right to provide just an overview here. The book closes with a brief appendix collecting facts from computational complexity and probability theory.
With some effort, one can think of minor criticisms: sometimes rather crucial proof steps are relegated to exercises, e.g., the fact of the integrality of the vertices of the "fractional $s$-$t$ cut polytope". But really this is nit-picking. Given the paucity of textbooks in this area, I would have been able to recommend this one even if it had merely done an adequate job. I am pleased to report that it does much more than this. It deserves a place in every computer science and mathematics library.
| © Copyright 2004, American Mathematical Society Privacy Statement |
