Paradigms for fast parallel approximability
著者
書誌事項
Paradigms for fast parallel approximability
（Cambridge international series on parallel computation, 8）
Cambridge University Press, c1997
- hbk.
- pbk.
大学図書館所蔵 件 / 全25件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index
内容説明・目次
内容説明
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.
「Nielsen BookData」 より