Browse Books

Reviewer: Dimitrios Katsaros

An excellent source of information for a young and exciting research field that of devising approximation algorithms for numerous NP-hard problems is provided in this book. The author has conducted premium quality research in various topics, and during the past ten years has advanced the field of approximation algorithms. This is an ideal introductory book for this field, written by a highly qualified author. The first of the books three parts covers combinatorial algorithms for a number of important problems. Among these problems are the set cover, the metric Steiner tree, the traveling salesperson, the knapsack, and the bin packing problems. The second part presents algorithms, which are based on the linear programming paradigm. These algorithms are categorized under two techniques: the rounding and the primal-dual schema. These schemes are exhibited using problems like the set cover, the facility location, and so on. Finally, the third part covers the problem of finding a shortest vector in a lattice, the approximability of counting the solutions of a given problem instance, the hardness of devising approximation algorithms for many key problems, and also some open problems of the field. Although it is tempting to comment on each part of the book individually, it is better to treat it as a whole. The book from the first glance reveals a great deal of insight about the authors very deep knowledge of the topic. This is immediately seen, if one considers the set of problems that were selected to present the ideas and fundamental techniques behind the approximability of algorithms. These problems are well known and occupy a central position in the teaching of any course related to the design of algorithms. The author has achieved a combination of mathematical precision and clarity of presentation, so that the final text is comprehensible without sacrificing mathematical elegance. Other advantages of the book are the set of exercises and the short notes at the end of each chapter. The exercises are indeed very instructive and sometimes very challenging; some more properly expressed hints would be needed to make them less frightening. The bibliographic notes are very useful, and provide links to additional reading. If someone wanted to find any negative aspects in this book, he would mention the non-cohesive appearance of the first part (which is also admitted by the author). Moreover, he would add the paper-like appearance of the other parts as well. But I believe that this is not necessarily a shortcoming. In such books, which are targeted for graduate studies or deal with advanced mathematical topics, a nice appearance is not the primary objective; it is the rigorous mathematical presentation that is striven for. I really enjoyed reading and studying this book. I am convinced it will be a must read for anyone who is involved in the task of designing algorithms. Online Computing Reviews Service