Search in Book Reviews

There are a range of problems in mathematics and computer science which cannot be computed, i.e. to solve them they have to be approximated. This book surveys techniques for approximating combinatorial problems using parallel algorithms. It starts with an introductory chapter, which defines the problem and presents basic concepts and techniques. Chapter two gives a formal presentation of algorithms for the PRAM (Parallel Random Access Machines) model, surveys results on sequential approximability and introduces parallel approximability. This is followed by four chapters presenting a set of paradigms to produce parallel approximations for a range of pro-blems (flows, coverings, matchings, graphs, travelling salesperson, pin packing, etc.) A final chapter looks at problems which cannot be approximated A very specialised book summarising research done in this topic. Required reading for researchers working on parallel algorithms and of interest to anyone working in the area of parallel computation in general. Also useful as a support text for final year undergraduate or postgraduate modules in either parallel or sequential algorithms.