Paradigms for Fast Parallel Approximability
Seiten
2009
Cambridge University Press (Verlag)
978-0-521-11792-0 (ISBN)
Cambridge University Press (Verlag)
978-0-521-11792-0 (ISBN)
This 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. This is an up-to-date reference for graduate students and researchers in algorithmics.
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.
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.
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.
| Erscheint lt. Verlag | 30.7.2009 |
|---|---|
| Reihe/Serie | Cambridge International Series on Parallel Computation |
| Zusatzinfo | 32 Line drawings, unspecified |
| Verlagsort | Cambridge |
| Sprache | englisch |
| Maße | 170 x 244 mm |
| Gewicht | 280 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Informatik ► Weitere Themen ► Hardware | |
| ISBN-10 | 0-521-11792-5 / 0521117925 |
| ISBN-13 | 978-0-521-11792-0 / 9780521117920 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
IT zum Anfassen für alle von 9 bis 99 – vom Navi bis Social Media
Buch | Softcover (2021)
Springer (Verlag)
CHF 41,95
Interlingua zur Gewährleistung semantischer Interoperabilität in der …
Buch | Softcover (2023)
Springer Fachmedien (Verlag)
CHF 46,15
Eine Einführung mit Java
Buch | Hardcover (2020)
dpunkt (Verlag)
CHF 62,85
