|
Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
 |
Author: G. Ausiello, P. Crescenzi, V. Kann, Marchetti-sp, Giorgio Gambosi
List Price: $71.95
Our Price: Click to see the latest and low price
ISBN: 3540654313
Publisher: Springer Verlag (January, 2000)
Edition: Hardcover
Sales Rank: 206,467
Average Customer Rating: 5 out of 5
|
Customer ReviewsRating: 5 out of 5
A great sequel to Garey and Johnson
This book is a great sequel to Garey and Johnson. The appendix of this book gives a list of all NP optimisation problems together with their current approximability (or inapproximability results) in a Garey Johnson fashion.Developing approximation algorithms for NP hard problems is now a very active field in Mathematical Programming and Theoretical Computer Science. There have been a number of exciting developments like semidefinite programming , the Goemans Williamson algorithm for max cut et al. On the other hand, from a theoretical computer science point of view, we now have a proof that many of these problems cannot have polynomial approximation algorithms unless P=NP. This book provides an excellent introduction to both areas. A worthy supplement to Garey and Johnson, Papadimitriou's books on combinatorial optimisation and computational complexity, Hochbaum's book on approximation algorithms, Alon and Spencer's book on the probabilistic method and finally Motwani and Raghavan's book on randomised algorithms.
Similar Products
· Approximation Algorithms for NP-Hard Problems
· Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)
· Randomized Algorithms
· Approximation Algorithms
|
