Paradigms for Fast Parallel Approximability [Paperback]

A survey of the basic techniques for approximating combinatorial problems using parallel algorithms.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 s alesman problems, graphs), but in order to make the book reasonably self-contained, the authors provide an introductory chapter containing the basic definitions and results. This will be a up-to-date reference for research workers in the area of algorithms, but it can also be used for graduate courses in the subject.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 s alesman problems, graphs), but in order to make the book reasonably self-contained, the authors provide an introductory chapter containing the basic definitions and results. This will be a up-to-date reference for research workers in the area of algorithms, but it can also be used for graduate courses in the subject.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, such as flows, coverings, matchings, traveling salesman problems, and graphs. For added clarity, 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 rounded off by an appendix that gives a convenient summary of the problems described in the book. This book is an up-to-date reference for research workers in the area of algorithmslL