Many well-known optimization problems are intractable, in the sense that optimal solutions are not computable within polynomial time. For these problems, an approximation algorithm is an efficient alternative that produces near-optimal solutions that are guaranteed to be within a fixed ratio of the optimal solution. Thus, in contrast to algorithms determining the exact optimal solution, for which the algorithm’s running time is the main measure, there is a second measure for approximation algorithms, which is the performance ratio measuring how close the approximation algorithm’s solution is to the optimal solution. The tradeoff between the running time and the performance ratio of an approximation algorithm is an important issue in the design of approximation algorithms, and different design techniques have been invented to address this. Due to the importance of the design techniques for the quality of near-optimal solutions by approximation algorithms, the authors have organized their book according to design methods rather than by application problems as in other books.

The first chapter is a brief introduction to notation, definitions, and concepts needed as a basis for the rest of the book. It starts with a definition of approximation algorithms in an intuitive yet mathematically rigorous way. Following this is an informal overview of design techniques for approximation algorithms, a discussion of the difference between heuristics and approximations, a description of the basics of computational complexity, a summary of nondeterministic polynomial-time (NP) complete problems, and the definition of performance ratios.

The central issue of the design of approximation algorithms is considered to be composed of two steps. First, the intractable optimization problem is converted into a tractable variation by perturbing the objective function, the feasible domain of possible solutions, or the input values. Second, an efficient exact solution algorithm is designed for the new tractable problem and its solution is converted back, if necessary. An example of perturbing the objective function is the greedy strategy, which is covered in chapter 2. The strategy may involve perturbation of the feasible domains by techniques such as restriction and relaxation. The techniques of restriction, including the partition and the guillotine-cut technique, are studied in chapters 3 through 5. The techniques of relaxation, including linear programming, the primal-dual method, the local ratio method, and semidefinite programming, are studied in chapters 6 through 9. Chapter 10 is devoted to inapproximability results, with fundamental concepts and results, often without proofs.

The book is intended for graduate courses of different levels, and course plans based on different chapter selections are proposed. Each chapter is accompanied by several pages of exercises and historical notes, setting the material and the references in context. The comprehensive bibliography covers a huge amount of literature in the heuristics and approximations area, as well as specific application problems. The index is detailed. This makes the book a good source for a course on approximation algorithms. Indeed, the material was expanded from lecture notes for various courses given by the authors at different universities. They note that the only prerequisite for reading the book is a familiarity with pseudocode, an informal high-level programming language similar to standard programming languages such as C, Java, or Pascal, without complicated constructs. However, the book might not be suitable for self-study by younger graduate students due to the advanced mathematical style. For the more advanced reader the book seems to be an excellent in-depth resource on approximation algorithms, from their beginning up to the latest developments.