Customer Reviews

Approximation Algorithms

5 star:		(8)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

I have been using Dorit Hochbaum's book on approximation algorithms for NP-Hard problems as a guideline for my work. Hochbaum's book is, without a doubt, terrific. However, the survey format compromised a smooth flow in favor of bringing together the best people in the field. This book (Vazirani's) corrects this by being so smooth and elegant from start to finish. Excellent problem sets, excellent hints for most problems, and there is a section at the end of the book devoted to open problems, which is a really really cool feature. My favorite chapter -29 I think- deals with hardness of approximation and the PCP theorem. The chapter explains the PCP theorem so vividly that the exact next thing I was doing was reading and comprehending the latest papers in this area. If you're a researcher in algorithms and complexity, then this book is highly recommended, especially at this ridiculously low price.
Note on my background: I am a graduate (masters) student in CS.

I have been looking for books related to solving NP-complete and NP-hard problems approximately. There is another book by Hochbaum and I have that too. Unfortunately, that book is more of a research oriented book as it is written by several researchers. It's like reading several research papers within two hard covers. This means that one needs to have a sort of intermediate level of experience with approximation algorithms.

For a beginner, one would expect a book that starts from ground-up and that has been written as a textbook rather than as a set of research papers. The book by Dr. Vazirani, is the only book that is written by one author with a step-by-step evolution of concepts and ideas related to approximation algorithms.

This is a quite nice book by an author who is well-known in the field. The book is not thematic, instead it presents certain problems in each chapter along with the main approximation algorithms and correctness proofs. Yet, each new concept is well introduced with the problems. For instance, the author presents LP-based techniques on the same problem (set cover) in the second part of the book. This makes it quite easy to compare and understand different techniques. The last part of the book is a little bit advanced compared to the first two parts which uses combinatorial or LP-based analysis of the algorithms. The presentation of the PCP theorem- arguably the deepest theorem of computer science- and its consequences are also in the last part.

A warning though: The book is quite terse at times, which enforces a dense reading. This may not be suitable for an undergradute study. My only complaint is that the PCP theorem might well be introduced with a little more intution.

Overall, I rate this book as excellent. If you are interested in algorithms, you should definitely buy it. Also, buy the "Complexity and Approximation" by Ausiello, Crescenzi and others. They provide a more comprehensive and thematic treatment. It also has an excellent bibliography and list of NP-hard problems. These two will make a great couple. The book edited by Hochbaum (Approximation Algorithms for NP-hard problems) on the other hand presents detailed information on the algorithms.

Very good, it is easy to read the book if you have a good level

of knowledge and the experience to think some details in the

proofs of the theorems.

I think it is a very good book for a graduate student.

This is not only the best Appoximation Algorithm book out there, its one of the best books on graduate level mathematics I have ever seen. Such eloquent coverage of advanced topics. I can not recommend it highly enough.

I have always been a operational research aficionado, but when I skimmed through this book the first time I did not really "get it". Then, I was led back to this book and now it has become one of those books I like to pick up just to bring the remembrance of the concepts it talks about. One main topic is duality and how for different problems we can squeeze the gap between the solution built in primal and dual space. I have known the theory for years, yet it is only more recently and with help among others from this book, that I start to get a glimpse of the whole depth and magic in this area of "applied" mathematics.

Let's be concrete.

The first part of the book presents a set of classical NP hard problems, set covering, bin packing, knapsack, etc. and their approximation algorithms. These algorithms are extracted from a number of fundamental papers, which are of long, delicate presentations. Vazirami presented the problems and solutions in a unified framework. The presentation appears much shorter than they were in the original papers, and they are concise, precise, explicit and comprehensive. For an algorithm researcher, if he read the book first and then those papers, he will be much more efficient than doing that other way (as I and many other people did.)

The second part of the book present the LP scheme of approximation algorithm design. I had little knowledge about this. But to pursue a career as an algorithm researcher, I must know this. Vazirani's book gives me a comprehensive (yet short) start.

I rarely give my reviews five stars (2% of my reviews get 5 stars so far), but this book deserves.

This is a fanastic topics book in approximation algorithms. The problems and proofs are challenging and concise, but written in a very accessible manner. It is a great reference book, and also a convenient place to grab a lecture from if you need something to fill our a course. I have found it extremely useful, and even fun to read. I highly reccomend it for any person interested in theoretical computer science.

Vazirani's book seems well suited for a computer science researcher who has had a rigorous background in pure maths. The level of difficulty can be quite advanced. Also, it is not the sort of book that gives algorithm examples in an actual programming language. Not that this should be a handicap to a skilled reader. The algorithms are usually described in high level pseudocode. You have to manually instantiate these in the language of your preference.

The 30 chapters span a wide variety of computational topics. Some are simpler than others to understand. Like the chapter on finding the shortest vector from the integer lattice made from a set of linearly independent vectors. That requires only a year or so of introductory linear algebra.

There are exercises for each chapter. Some exercises are formidable. Essentially like little research problems in their own right. Another plus for the book.