Approximation algorithms are used to find near-optimal solutions to some hard optimization problems. For “inapproximable” problems, metaheuristics methodologies are proposed. A lot of research has already been conducted, but the fight against complexity continues.

This book is what a reader needs if he or she is interested in hard optimization problems for traditional or modern applications (packing, facility location, traveling salesman, Steiner trees, scheduling, assignment, and satisfiability); computational geometry and graph-based applications (triangulations, connectivity, decomposition, partitioning, planarity, spanning trees, clustering, vital edges, and disjoint paths); and large-scale and emerging applications (networking, micro-array analysis, sequence alignment, economic equilibrium, virtual communities, and color quantization).

Gonzalez has made great contributions to solving many of the above problems. He has cooperated with a large number of researchers in order to capture the fundamentals of approximation algorithms and metaheuristics methodologies, and to present and analyze recent research results concerning the solving of the above-mentioned problems.

The material is organized into six parts, divided into chapters. Each chapter is written by one or more researchers, and can be read as an extended article, starting with an introduction to the field, research details about the subject, conclusions/discussions, and references. Several chapters outline open problems, and some are dedicated to algorithms, their complexity, and applications.

Being a “hard” book for “hard” problems, a chapter-by-chapter presentation would be too long. I will provide details for the first 31 chapters, comprising Parts 1 through 3, which cover the most frequently used techniques for designing and analyzing algorithms. Chapters 32 through 86, comprising Parts 4 through 6, address the portfolio of applications mentioned above.

Part 1 consists of 17 chapters, and is dedicated to the basic methodologies for designing and analyzing approximation algorithms and metaheuristics. Gonzalez presents an overview of approximation algorithms and metaheuristics, and introduces the notations and terminology in chapter 1; more details and applications in chapter 2; and methods based on the restriction technique in chapter 3. Khuller et al. provide a detailed analysis of greedy methods in chapter 4. Even analyzes recursive greedy methods and formulates open problems in chapter 5. The role of linear programming (LP) in designing and analyzing combinatorial approximation algorithms is presented in chapters 6 and 7, by Rabani for randomized rounding, and by Gaur and Krishnamurti for both deterministic and nondeterministic rounding, respectively. Complex quadratic optimization problems are considered in chapter 8 by So, Ye, and Zhang. Chapter 9, by Shachnai and Tamir, covers polynomial-time approximation schemes. In chapter 10, Sahni reviews three general transformation methods: rounding, interval partitioning, and separation. Asymptotic fully polynomial-time approximation schemes are introduced and analyzed by Motwani, O’Callaghan, and Zhu in chapter 11. Nikoletseas and Spirakis describe randomized approximation techniques, including those based on Markov chain Monte Carlo (MCMC) methods, in chapter 12. LP-duality and randomization techniques used to create efficient distributed algorithms are described in chapter 13, by Dubhashi et al. In chapter 14, Hoos and Stützle present empirical approaches based on computational experiments, which are used for the analysis of randomized algorithms. Ausiello and Paschos describe transformations (called reductions) that preserve approximability in chapter 15, and introduce the differential approximation ratio for measuring the quality of solutions obtained by approximation algorithms in chapter 16. Szegedy treats the core theory of inapproximability in chapter 17.

Part 2, consisting of ten chapters, deals with local search, neural networks (NNs), and more metaheuristics. In chapter 18, Solis-Oba describes the use of local search techniques for solving different optimization problems, including multiprocessor scheduling and clustering problems. Hoos and Stützle review simple stochastic local search (SLS) methods, hybrid SLS, and population-based SLS methods (ant colony optimization and evolutionary algorithms) in chapter 19; research directions are also discussed. In chapter 20, Ahuja et al. discuss techniques for developing very large-scale neighborhood search algorithms for traditional and specific applications. In chapter 21, by Battiti and Brunato, reactive search methods for machine learning memory-based heuristics are introduced, analyzed, and applied for solving optimization problems. DasGupta et al. develop “real-time backpropagation through time” recurrent NNs as learning mechanisms, and discuss the computational capabilities of discrete and continuous recurrent networks, in chapter 22. Chapter 23, by Glover et al., is dedicated to Tabu search; principles and new variants are considered for implementation and testing. Leguizamón et al. write a summary of evolutionary computation techniques in the context of metaheuristics, presented in connection with new trends, in chapter 24. Aarts et al. discuss simulated annealing in chapter 25. The ant colony optimization approach, inspired by the real-life behavior of ants, is introduced by Dorigo and Socha in chapter 26; current research directions are also discussed. Moscato and Cotta explain memetic algorithms in chapter 27, showing not only the memetic algorithm structure, but also its power for solving combinatorial optimization problems.

Part 3 deals with multiobjective optimization, sensitivity analysis, and stability. It has only four chapters. In chapter 28, Angel et al. consider multiobjective combinatorial optimization problems (MCOP) and describe three classes of multiobjective approximation methods, including simultaneous and Pareto-set approaches. Paquete and Stützle present a review of SLS algorithms for MCOPs in chapter 29. Chapter 30 deals with sensitivity analysis when solving MCOPs. This chapter, written by Fernández-Baca and Venkatachalam, covers aspects related to both polynomially solvable problems and nondeterministic polynomial-time (NP) hard problems. Böckenhauer et al., in chapter 31, define the stability of approximation algorithms and present stable approximation algorithms for some optimization problems.

The book has a very good index, containing the most important keywords related to approximation algorithms and metaheuristic methodologies.

Many of the chapters require graduate-level knowledge. The book is a research and reference tool, and not suitable for use as a classroom textbook.

This is an important work. The editor brings together almost all known approaches to approximation algorithms and metaheuristics. The handbook is a start-up resource for young researchers, and a valuable reference for people with advanced knowledge. I recommend this book not only for reading, but also as a handy reference guide.