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 algorithms and for graduate courses in the subject.
Author(s): Josep Díaz, Maria Serna, Paul Spirakis, Jacobo Torán
Series: Cambridge international series on parallel computation 8
Publisher: Cambridge University Press
Year: 1997
Language: English
Pages: 167
City: Cambridge; New York
Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents ......Page 6
Preface ......Page 8
1 Introduction ......Page 10
1.1 Sequential and Parallel Computation ......Page 11
1.2 Some Problems to Approximate ......Page 13
1.3 Realistic Models ......Page 18
2.1 The PRAM Model of Computation ......Page 21
2.2 Randomized PRAM Computation ......Page 23
2.3 P-Completeness ......Page 28
2.4 Approximation Algorithms ......Page 31
2.5 Parallel Approximation Classes ......Page 33
2.6 Approximation Preserving Reductions ......Page 35
2.7 Pseudo-NC Algorithms and Approximation ......Page 37
3 Extremal Graph Properties ......Page 41
3.1 The Induced Subgraph of High Weight is in NCX ......Page 42
3.2 Examples of Linear Extremal Graph Properties ......Page 44
4 Rounding, Interval Partitioning and Separation ......Page 48
4.1 The Subset Sum Problem ......Page 50
4.2 Maximum Flow and Weighted Matching ......Page 52
4.3 Approximating Maximum Flow ......Page 58
4.4 Approximating Maximum Weight Matching ......Page 60
4.5 NC Approximations to Flows and Matchings ......Page 62
5 Primal-Dual Method ......Page 64
5.1 Positive Linear Programming ......Page 65
5.2 Further Applications ......Page 72
5.3 The Vertex Cover Problem ......Page 73
6 Graph Decomposition ......Page 77
6.1 Planar Graphs ......Page 78
6.2 The Maximum Independent Set for Outerplanar Graphs ......Page 83
6.3 The Maximum Independent Set for k-Outerplanar Graphs ......Page 93
6.4 The Maximum Independent Set problem for Planar Graphs ......Page 101
7.1 The Minimum Metric Traveling Salesperson Problem ......Page 103
7.2 Bin Packing ......Page 106
7.3 More Cut Problems ......Page 114
7.4 Other Problems ......Page 115
8 Non-Approximability ......Page 117
8.1 The High Connected Subgraph Problem ......Page 118
8.2 Linear Programming ......Page 127
8.3 The Nearest Neighbor Heuristic ......Page 133
9 Syntactically Defined Classes ......Page 137
9.1 MaxNP and MaxSNP ......Page 138
9.2 Limits for the Approximation ......Page 142
Appendix 1 Definition of Problems ......Page 146
Bibliography ......Page 154
Author index ......Page 162
Subject index ......Page 164
