Paradigms for fast parallel approximability

Author(s)

Bibliographic Information

Paradigms for fast parallel approximability

Josep Díaz ... [et al.]

(Cambridge international series on parallel computation, 8)

Cambridge University Press, c1997

  • hbk.
  • pbk.

Available at  / 24 libraries

Search this Book/Journal

Note

Includes bibliographical references and index

Description and Table of Contents

Description

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.

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.

by "Nielsen BookData"

Related Books: 1-1 of 1

Details

Page Top