Overview

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.

Full Product Details

Author:   Giorgio Ausiello ,  Pierluigi Crescenzi ,  Giorgio Gambosi ,  Viggo Kann
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   1st ed. 1999. Corr. 2nd printing 2002
Dimensions:   Width: 20.30cm , Height: 3.80cm , Length: 25.40cm
Weight:   1.381kg
ISBN:  

9783540654315

ISBN 10:   3540654313
Pages:   524
Publication Date:   09 November 1999
Audience:   College/higher education ,  Professional and scholarly ,  Postgraduate, Research & Scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   Awaiting stock  
The supplier is currently out of stock of this item. It will be ordered for you and placed on backorder. Once it does come back in stock, we will ship it out for you.

Table of Contents

1 The Complexity of Optimization Problems.- 1.1 Analysis of algorithms and complexity of problems.- 1.2 Complexity classes of decision problems.- 1.3 Reducibility among problems.- 1.4 Complexity of optimization problems.- 1.5 Exercises.- 1.6 Bibliographical notes.- 2 Design Techniques for Approximation Algorithms.- 2.1 The greedy method.- 2.2 Sequential algorithms for partitioning problems.- 2.3 Local search.- 2.4 Linear programming based algorithms.- 2.5 Dynamic programming.- 2.6 Randomized algorithms.- 2.7 Approaches to the approximate solution of problems.- 2.8 Exercises.- 2.9 Bibliographical notes.- 3 Approximation Classes.- 3.1 Approximate solutions with guaranteed performance.- 3.2 Polynomial-time approximation schemes.- 3.3 Fully polynomial-time approximation schemes.- 3.4 Exercises.- 3.5 Bibliographical notes.- 4 Input-Dependent and Asymptotic Approximation.- 4.1 Between APX and NPO.- 4.2 Between APX and PTAS.- 4.3 Exercises.- 4.4 Bibliographical notes.- 5 Approximation through Randomization.- 5.1 Randomized algorithms for weighted vertex cover.- 5.2 Randomized algorithms for weighted satisfiability.- 5.3 Algorithms based on semidefinite programming.- 5.4 The method of the conditional probabilities.- 5.5 Exercises.- 5.6 Bibliographical notes.- 6 NP, PCP and Non-approximability Results.- 6.1 Formal complexity theory.- 6.2 Oracles.- 6.3 The PCP model.- 6.4 Using PCP to prove non-approximability results.- 6.5 Exercises.- 6.6 Bibliographical notes.- 7 The PCP theorem.- 7.1 Transparent long proofs.- 7.2 Almost transparent short proofs.- 7.3 The final proof.- 7.4 Exercises.- 7.5 Bibliographical notes.- 8 Approximation Preserving Reductions.- 8.1 The World of NPO Problems.- 8.2 AP-reducibility.- 8.3 NPO-completeness.- 8.4 APX-completeness.- 8.5 Exercises.- 8.6 Bibliographical notes.- 9 Probabilistic analysis of approximation algorithms.- 9.1 Introduction.- 9.2 Techniques for the probabilistic analysis of algorithms.- 9.3 Probabilistic analysis and multiprocessor scheduling.- 9.4 Probabilistic analysis and bin packing.- 9.5 Probabilistic analysis and maximum clique.- 9.6 Probabilistic analysis and graph coloring.- 9.7 Probabilistic analysis and Euclidean TSP.- 9.8 Exercises.- 9.9 Bibliographical notes.- 10 Heuristic methods.- 10.1 Types of heuristics.- 10.2 Construction heuristics.- 10.3 Local search heuristics.- 10.4 Heuristics based on local search.- 10.5 Exercises.- 10.6 Bibliographical notes.- A Mathematical preliminaries.- A.1 Sets.- A.1.1 Sequences, tuples and matrices.- A.2 Functions and relations.- A.3 Graphs.- A.4 Strings and languages.- A.5 Boolean logic.- A.6 Probability.- A.6.1 Random variables.- A.7 Linear programming.- A.8 Two famous formulas.- B A List of NP Optimization Problems.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions