Complexity and Approximation

Collectif d'auteurs

524 pages, parution le 17/02/2003

Ajouter à une liste

Indisponible

Résumé

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.

Contents

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

L'auteur - Collectif d'auteurs

Autres livres de Collectif d'auteurs

Daniel Buren, mot à mot

Familles. Permanence et métamorphoses

Architecture studio

Structuration et management des organisations

Découvrir tous les livres de Collectif d'auteurs

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Collectif d'auteurs
Parution	17/02/2003
Nb. de pages	524
Format	20 x 24,5
Couverture	Relié
Poids	1185g
Intérieur	Noir et Blanc
EAN13	9783540654315