Paradigms for fast parallel approximability /
Díaz, J. 1950-
Paradigms for fast parallel approximability / Josep Díaz [and others]. - Cambridge : Cambridge University Press, 1997. - 1 online resource (viii, 158 pages) : digital, PDF file(s). - Cambridge international series on parallel computation ; 8 . - Cambridge international series on parallel computation ; 8. .
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.
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.
9780511666407 (ebook)
Parallel processing (Electronic computers)
QA76.58 / .D53 1997
511/.6/0285435
Paradigms for fast parallel approximability / Josep Díaz [and others]. - Cambridge : Cambridge University Press, 1997. - 1 online resource (viii, 158 pages) : digital, PDF file(s). - Cambridge international series on parallel computation ; 8 . - Cambridge international series on parallel computation ; 8. .
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.
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.
9780511666407 (ebook)
Parallel processing (Electronic computers)
QA76.58 / .D53 1997
511/.6/0285435