Buch, Englisch, Band 8, 168 Seiten, Format (B × H): 170 mm x 244 mm, Gewicht: 302 g
Reihe: Cambridge International Series on Parallel Computation
Buch, Englisch, Band 8, 168 Seiten, Format (B × H): 170 mm x 244 mm, Gewicht: 302 g
Reihe: Cambridge International Series on Parallel Computation
ISBN: 978-0-521-11792-0
Verlag: Cambridge University Press
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.
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Funktionale, Logische, Parallele und Visuelle Programmierung
- Mathematik | Informatik EDV | Informatik Technische Informatik Grid-Computing & Paralleles Rechnen
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
Weitere Infos & Material
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.
