Josep Díaz, Maria Serna, Paul Spirakis

Paradigms for Fast Parallel Approximability

• Gebundenes Buch

Produktbeschreibung

Various problems in computer science are 'hard', that is NP-complete, and so not realistically computable; thus in order to solve them they have to be approximated. This book is a survey of the basic techniques for approximating combinatorial problems using parallel algorithms. Its core is a collection of techniques that can be used to provide parallel approximations for a wide range of problems (for example, flows, coverings, matchings, travelling salesman problems, graphs), but in order to make the book reasonably self-contained, the authors provide an introductory chapter containing the basic definitions and results. A final chapter deals with problems that cannot be approximated, and the book is ended by an appendix that gives a convenient summary of the problems described in the book. This is an up-to-date reference for research workers in the area of algorithms, but it can also be used for graduate courses in the subject.

Produktdetails

• Cambridge International Parall Nr.8
• Verlag: Cambridge University Press
• New
• Seitenzahl: 166
• Erscheinungstermin: August 1997
• Englisch
• Abmessung: 249mm x 175mm x 15mm
• Gewicht: 454g
• ISBN-13: 9780521431705
• ISBN-10: 0521431700
• Artikelnr.: 35675656

Inhaltsangabe

1. Introduction
2. Basic concepts
3. Extremal graph properties
4. Rounding, interval partitioning and separation
5. Primal-dual method
6. Graph decomposition
7. Further parallel approximations
8. Non-approximability
9. Syntactical defined phrases
Appendix: Definition of problems
Bibliography
Index.