L'événement

.

LES NOUVEAUX OUTILS DE L'ENTREPRISE DE DEMAIN

de Philippe Mounier

LES NOUVEAUX OUTILS DE L'ENTREPRISE DE DEMAIN




 


email ou code client :
mot de passe :
* Oublié ?

Première visite ?
Demander un devis
Créer un compte
Frais de port
à 1 euros
pour les particuliers
à partir de 50 euros
(France métropolitaine uniquement)

Ajouter cet article au panier

Nbre d'exemplaires:

Computers and Intractability: A Guide to the Theory of Np-Completeness

Titre :

Computers and Intractability: A Guide to the Theory of Np-Completeness

Caractéristiques :


Auteur(s) :GAREY
Editeur :W.H.FREEMAN
Parution :10/1979
Langue :Anglais Anglais
Nbre de pages :338
ISBN :978-0-7167-1045-5
Reliure :Paperback
Prix :141.00 € ttc
Disponibilité :Livraison sous 2 à 10 jours ouvrables.

Couverture :


Computers and Intractability: A Guide to the Theory of Np-Completeness

Résumé :

Few technical terms have gained such rapid notoriety as the appela-
tion "NP-complete." In the short time since its introduction in the early
197015, this term has come to symbolize the abyss of inherent intractability
that algorithm designers increasingly face as they seek to solve larger and
more complex problems. A wide variety of commonly encountered prob-
lems from mathematics, computer science, and operations research are now
known to be NP-complete, and the collection of such problems continues to
grow almost daily. Indeed, the NP-complete problems are now so pervasive
that it is important for anyone concerned with the computational aspects of
these fields to be familiar with the meaning and implications of this concept.
This book is intended as a detailed guide to the theory of NP-
completeness, emphasizing those concepts and techniques that seem to be
most useful for applying the theory to practical problems. It can be viewed
as consisting of three parts.
The first part, Chapters 1 through 5, covers the basic theory of NP-
completeness. Chapter 1 presents a relatively low-level introduction to
some of the central notions of computational complexity and discusses tl~e
significance of NP-completeness in this context. Chapters 2 through 5 pro-
vide the detailed definitions and proof techniques necessary for thoroughly
understanding and applying the theory.
The second part, Chapters 6 and 7' provides an overview of two al-
ternative directions for further study. Chapter 6 concentrates on the search
for efficient 'approximation" algorithms for NP-complete problems, an area
whose development has seen considerable interplay with the theory of NP-
completeness. Chapter 7 surveys a large number of theoretical topics in
computational complexity, many of which have arisen as a consequence of
previous work on NP-completeness. Both of these chapters (especially
Chapter 7) are intended solely as introductions to these areas, wit 10 our ex-
pectation being that any reader wishing to pursue particular topics in more
detail will do so by consulting the cited references.
The third and final part of the book is the Appendix, which contains
an extensive list (more than 300 main entries, and several times this many
results in total) of NP-complete and NP-hard problems. Annotations to the
main entries discuss what is known about the complexity of subproblems
and variants of the stated problems.
The book should be suitable for use as a supplementary text in
courses on algorithm design, computational complexity, operations research,
or combinatorial mathematics. It also can be used as a starting point for
seminars on approximation algorithms or computational complexity at the
graduate or advanced undergraduate level. The second author has used a
preliminary draft as the basis for a graduate seminar on approximation algo-
rithms, covering Chapters 1 through 5 in about five weeks and then pursu-
ing the topics in Chapter 6, supplementing them extensively with additional
material from the references. A seminar on computational complexity
might proceed similarly, substituting Chapter 7 for Chapter 6 as the initial
access point to the literature. It is also possible to cover both chapters in a
combined seminar.
More generally, the book can serve both as a self-study text for any-
one interested in learning about the subject of NP-completeness and as a
reference book for researchers and practitioners who are concerned with al-
gorithms and their complexity. The list of NP-complete problems in the
Appendix can be used by anyone familiar with the central notions of NP-
completeness, even without having read the material in the main text. The
novice can gain such familiarity by skimming the material in Chapters 1
through 5, concentrating on the informal discussions of definitions and
techniques, and returning to the more formal material only as needed for
clarification. To aid those using the book as a reference, we have included a
substantial number of terms in the Subject Index, and the extensive Refer-
ence and Author Index gives the sections where each reference is men-
tioned in the text.
We are indebted to a large number of people who have helped us
greatly in preparing this book. Hal Gabow, Larry Landweber, and Bob Tar-
jan taught from preliminary versions of the book and provided us with valu-
able suggestions based on their experience. The following people read pre-
liminary drafts of all or part of the book and made constructive comments:
Al Aho, Shimon Even, Ron Graham, Harry Hunt, Victor Klee, Albert
Meyer, Christos Papadimitriou, Henry Pollak, Sartaj Sahni, Ravi Sethi, Lar-
ry Stockmeyer, and Jeff UlIman. A large number of researchers, too
numerous to mention here (but see the Reference and Author Index),
responded to our call for NP-completeness results and contributed toward
making our list of NP-complete problems as extensive as it is. Several of
our colleagues at Bell Laboratories, especially Brian Kernighan, provided in-
valuable assistance with computer typesetting on the UNIX@ system. Final-
ly, special thanks go to Jeanette Reinbold, whose facility with translating
our handwritten hieroglyphics into faultless input to the typesetting system
made the task of writing this book so much easier.

Murray Hill, New Jersey -MICHAEL R. GAREY
October, 1978 DAVID S. JOHNSON

Table des matières :

Ces informations ne sont pas disponibles.

Ajouter cet article au panier

Nbre d'exemplaires: