Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties / Edition 1

Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties / Edition 1

by Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann
     
 

ISBN-10: 3540654313

ISBN-13: 9783540654315

Pub. Date: 12/03/2002

Publisher: Springer Berlin Heidelberg

In the last ten years the area concerned with the design of approximation algorithms and with the study of the approximability properties of NP-hard combinatorial optimization problems has been one of the most active in computer science, and its scientific developments have considerably enriched our understanding of problem complexity and our ability to cope with…  See more details below

Overview

In the last ten years the area concerned with the design of approximation algorithms and with the study of the approximability properties of NP-hard combinatorial optimization problems has been one of the most active in computer science, and its scientific developments have considerably enriched our understanding of problem complexity and our ability to cope with difficult applications." "This textbook features a compendium documenting the results on the approximability of more than 200 problems; thus the book is also a source of reference for professionals applying advanced optimization and approximation techniques in practice. The CD-ROM included contains a lot of valuable information, such as lecture slides in various data formats, the compendium in electronic version, and the algorithms visualization toolkit JAZ.

Product Details

ISBN-13:
9783540654315
Publisher:
Springer Berlin Heidelberg
Publication date:
12/03/2002
Edition description:
1st ed. 1999. Corr. 2nd printing 2002
Pages:
524
Product dimensions:
7.99(w) x 10.00(h) x 0.06(d)

Table of Contents

1The Complexity of Optimization Problems1
2Design Techniques for Approximation Algorithms39
3Approximation Classes87
4Input-Dependent and Asymptotic Approximation123
5Approximation through Randomization153
6NP, PCP and Non-approximability Results175
7The PCP theorem207
8Approximation Preserving Reductions253
9Probabilistic analysis of approximation algorithms287
10Heuristic methods321
AMathematical preliminaries353
BA List of NP Optimization Problems367
Bibliography471
Index515

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >