TY  - BOOK
AU  - Díaz,J.
TI  - Paradigms for fast parallel approximability
T2  - Cambridge international series on parallel computation
SN  - 9780511666407 (ebook)
AV  - QA76.58 .D53 1997
U1  - 511/.6/0285435 21
PY  - 1997///
CY  - Cambridge
PB  - Cambridge University Press
KW  - Parallel processing (Electronic computers)
N1  - Title from publisher's bibliographic system (viewed on 05 Oct 2015); Basic concepts --; Extremal graph properties --; Rounding, interval partitioning and separation --; Primal-dual method --; Graph decomposition --; Further parallel approximations --; Non-approximability --; Syntactically defined classes
N2  - 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
UR  - https://doi.org/10.1017/CBO9780511666407
ER  -