Paradigms for Fast Parallel Approximability

by Josep Díaz , Maria Serna , Paul Spirakis , Jacobo Torán

• ISBN13: 9780521431705
• ISBN10: 0521431700
• Format: Hardcover
• Copyright: 1997-08-28
• Publisher: Cambridge University Press

Summary

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

Preface	vii
1 Introduction	1	(11)
1.1 Sequential and Parallel Computation	2	(2)
1.2 Some Problems to Approximate	4	(5)
1.3 Realistic Models	9	(3)
2 Basic Concepts	12	(20)
2.1 The PRAM Model of Computation	12	(2)
2.2 Randomized PRAM Computation	14	(5)
2.3 P-Completeness	19	(3)
2.4 Approximation Algorithms	22	(2)
2.5 Parallel Approximation Classes	24	(2)
2.6 Approximation Preserving Reductions	26	(2)
2.7 Pseudo-NC Algorithms and Approximation	28	(4)
3 Extermal Graph Properties	32	(7)
3.1 The Induced Subgraph of High Weight is in NCX	33	(2)
3.2 Examples of Linear Extremal Graph Properties	35	(4)
4 Rounding, Interval Partitioning and Separation	39	(16)
4.1 The Subset Sum Problem	41	(2)
4.2 Maximum Flow and Weighted Matching	43	(6)
4.3 Approximating Maximum Flow	49	(2)
4.4 Approximating Maximum Weight Matching	51	(2)
4.5 NC Approximations to Flows and Matchings	53	(2)
5 Primal-Dual Method	55	(13)
5.1 Positive Linear Programming	56	(7)
5.2 Further Applications	63	(1)
5.3 The Vertex Cover Problem	64	(4)
6 Graph Decomposition	68	(26)
6.1 Planar Graphs	69	(5)
6.2 The Maximum Independent Set for Outerplanar Graphs	74	(10)
6.3 The Maximum Independent Set for k-Outerplanar Graphs	84	(8)
6.4 The Maximum Independent Set problem for Planar Graphs	92	(2)
7 Further Parallel Approximations	94	(14)
7.1 The Minimum Metric Traveling Salesperson Problem	94	(3)
7.2 Bin Packing	97	(8)
7.3 More Cut Problems	105	(1)
7.4 Other Problems	106	(2)
8 Non-Approximability	108	(20)
8.1 The High Connected Subgraph Problem	109	(9)
8.2 Linear Programming	118	(6)
8.3 The Nearest Neighbor Heuristic	124	(4)
9 Syntactically Defined Classes	128	(9)
9.1 MaxNP and MaxSNP	129	(4)
9.2 Limits for the Approximation	133	(4)
Appendix 1 Definition of Problems	137	(8)
Bibliography	145	(8)
Author index	153	(2)
Subject index	155