Paradigms for Fast Parallel ApproximabilityPaperback Cambridge International Series on Parallel Computation
List price $45.29
You save $2.30 (5%)
Free delivery worldwide
Dispatched in 3 business days
When will my order arrive?
- Publisher: CAMBRIDGE UNIVERSITY PRESS
- Format: Paperback | 168 pages
- Dimensions: 170mm x 241mm x 10mm | 295g
- Publication date: 30 July 2009
- Publication City/Country: Cambridge
- ISBN 10: 0521117925
- ISBN 13: 9780521117920
- Edition: 1
- Illustrations note: 32 b/w illus.
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.
Other books in this category
$19.50 - Save $5.48 21% off - RRP $24.98
$30.41 - Save $20.36 40% off - RRP $50.77
$33.34 - Save $5.70 14% off - RRP $39.04
$33.38 - Save $7.22 17% off - RRP $40.60
$55.77 - Save $16.07 22% off - RRP $71.84
$37.18 - Save $8.11 17% off - RRP $45.29
Review of the hardback: 'Required reading for researchers working on parallel algorithms and of interest to anyone working in the area of parallel computing in general.' Brian Bramer, CVu
Table of contents
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.