Paul Spirakis

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.

The ultimate goal of research in Distributed Computing is to understand the nature, properties and limits of computing in a system of autonomous communicating agents. To this end, it is crucial to identify those factors which are significant for the computability and the communication complexity of problems. A crucial role is played by those factors which can be termed Structural Information: its identification, characterization, analysis, and its impact on communication complexity is an important theoretical task which has immediate practical importance. The purpose of the Colloquia on Structural Information and Communication Complexity (SIROCCO) is to focus explicitly on the interaction between structural information and communication complexity. The Colloquia comprise position papers, presentations of current research, and group discussions. Series 1 contains papers presented at the 1st Colloquium on Structural Information and Communication Complexity, held in Ottawa, Canada. Series 2 contains papers presented at the 2nd Colloquium held in Olympia, Greece.