Approximation Algorithms (Hardcover)

~ (Author)

Editorial Reviews

Product Description

Approximation algorithms are currently a central and fast-developing area of research in theoretical computer science. This monograph covers the basic techniques used in the latest research work, techniques that everyone in the field should know, and shows that they form the beginnings of a promising theory. The author consolidates progress made so far, including some very recent results, and makes a strong effort to convey the beauty and excitement of work in the field.

Product Details

• Hardcover: 256 pages
• Publisher: Springer; Corrected edition (March 22, 2004)
• Language: English
• ISBN-10: 3540653678
• ISBN-13: 978-3540653677
• Product Dimensions: 9.4 x 6.3 x 1 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 4.8 out of 5 stars  See all reviews (6 customer reviews)
• Amazon.com Sales Rank: #58,223 in Books (See Bestsellers in Books)

  Popular in these categories: (What's this?)

  #4 in	Books > Professional & Technical > Professional Science > Mathematics > Pure Mathematics > Combinatorics
  #5 in	Books > Science > Mathematics > Pure Mathematics > Combinatorics
  #8 in	Books > Science > Mathematics > Pure Mathematics > Discrete Mathematics

Customer Reviews

Most Helpful Customer Reviews

47 of 47 people found the following review helpful:

5.0 out of 5 stars No approximations, this is THE optimal book!, February 16, 2002

By	Mosta McKracken (Cambridge, MA USA) - See all my reviews

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.

6 of 6 people found the following review helpful:

5.0 out of 5 stars Very nice introduction, May 19, 2006

By	Ali Civril (Troy, NY USA) - See all my reviews (REAL NAME)

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.

6 of 6 people found the following review helpful:

5.0 out of 5 stars Much needed desktop reference for anyone working with algorithms, networking protocols, optimization, March 8, 2006

By	M. Kochhal "mk" (Detroit, MI, USA) - See all my reviews (REAL NAME)

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.