Approximation Algorithms for NP-Hard Problems

Rating:
Summary: A good survey on approximation algorithms
Review: Developing approximation algorithms for NP hard problems is now a very active field in Mathematical Programming and Theoretical Computer Science. This book is actually a collection of survey articles written by some of the foremost experts in this field.

Many of these developments are due to Mathemtical programming (primal dual, semidefinite programming et al). The most exciting of these has been the Goemans and Williamson algorithm for MAX CUT and MAX SAT. A good account of these techniques appears in Chapters 4 and 11.

On the other hand a sequence of unexpected results in complexity culminated in a proof that many of these problems cannot have polynomial approximation algorithms unless P=NP. A good survey of "Hardness of Approximations" appears in Chapter 10, written by Sanjeev Arora and Carsten Lund both of whom were responsible for some original developments in this field.

I am going to purchase a copy of this book and can only strongly recommend it to everyone.