Complexity and Approximation

This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensible source of reference for professionals. The smooth integration of numerous illustrations, examples, and exercises make this monograph an ideal textbook.

• The Complexity of Optimization Problems
• Design Techniques for Approximation Algorithms
• Approximation Classes
• Input-Dependent and Asymptotic Approximation
• Approximation through Randomization
• NP, PCP and Non-approximability Results
• The PCP theorem
• Approximation Preserving Reductions
• Probabilistic analysis of approximation algorithms
• Heuristic methods
• A Mathematical preliminaries
• B A List of NP Optimization Problems
• Bibliography