A principal use of concurrent programming is in the implementation of distributed systems. A distributed system consists of processes running in different address spaces on logically different processors. Because the processes are physically disjoint, there are a number of issues that arise in distributed systems that are not present in concurrent programming:

• Communication latency is significantly higher over a network than between threads running in the same address space.

• Processors and network links can go down, and come back up, during the execution of a distributed program.

• Programs running on different nodes may be compiled independently, which means that type security cannot be guaranteed statically.

For these reasons, the synchronous model used in CML does not map well to the distributed setting. A different programming model is required for dealing with remote communication.

Although concurrent programming languages, such as CML, may not directly provide a notation for distributed programming, they do have an important rôle in implementing distributed systems. A distributed system is made up of individual programs running on different machines, which must communicate with each other. Managing this communication is easier in a concurrent language. Furthermore, multiple threads of control can help hide the latency of network communication. For these reasons, most distributed programming languages and toolkits provide concurrent programming features.

This chapter explores a distributed implementation of Linda-style tuple spaces (described in Section 2.6.3).

Concurrent programming differs from sequential programming in several significant ways. Conceptually, we can view the execution of a concurrent program as an interleaving of the sequential execution of its constituent processes. Since there are many possible interleavings, the execution of a concurrent program is nondeterministic; i.e., different interleavings may produce different results. In effect, a concurrent program defines a partial order on its actions, whereas a sequential program defines a total order. This nondeterminism is both the bane and boon of concurrent programming: on the one hand, it creates additional correctness problems, while on the other hand, it provides flexibility and a more natural program structure. As argued in Chapter 1, the choice of programming notation can help the programmer control the complexity of concurrency, while reaping its benefits.

A concurrent language typically consists of a sequential core (or sub-language), extended with support for concurrency. The concurrency support can be divided into three different kinds of mechanism:

• • A mechanism for introducing independent sequential threads of control, called processes. The process creation mechanism can be either static, restricting the program to a fixed number of processes, or dynamic, allowing new processes to be created “on-the-fly.”

• • A mechanism for processes to communicate. Communication involves exchanging data, either through shared memory locations (e.g., variables) or by explicit message passing.

• • And a mechanism for processes to synchronize. Synchronization restricts the ordering of execution in otherwise independent threads, and is used to limit the program's nondeterminism where necessary.

This chapter is the first of three tutorial chapters on the basic features and programming techniques of CML. This chapter focuses on the features that make up CML's semantic core. The next chapter continues with a discussion of the two most important styles of CML programming: process networks and client-server protocols. Chapter 5 completes the tutorial with further discussion of CML's synchronization and communication mechanisms.

Sequential programming

As is the case with most concurrent languages, CML consists of a sequential core language — Standard ML — extended with concurrency primitives. The individual processes in a CML program are programmed using the features of SML. While we conceptually view CML as a programming language, it is actually implemented as a collection of modules on top of SML/NJ. The aspects of CML described in this chapter all belong to the core structure of this library, which is named CML. To reduce notational clutter, most of the examples in this chapter are assumed to be given in an environment where the CML structure has been pre-opened (i.e., all of its bindings are at top-level). The CML structure's interface is described in Appendix A, which contains an abridged version of the CML Reference Manual.

CML is a message-passing language, which means that processes are viewed as executing in independent address spaces with their only communication being via messages. But, since SML provides updatable references, this is a fiction that must be maintained by programming style and convention.

In this chapter we present some problems for which their NC approximations are obtained using other techniques like “step by step” parallelization of their sequential approximation algorithms. This statement does not implythat the PRAM implementation is trivial. In some cases, several tricks must be used to get it. A difference from previous chapters is the fact that we shall also consider “heuristic” algorithms. In the first section we present two positive parallel approximation results for the Minimum Metric Traveling Salesperson problem. We defer the non-parallel approximability results on the Minimum Metric Traveling Salesperson problem until the next chapter. The following section deals with an important problem we already mentioned at the end of Section 4.1; the Bin Packing problem. We present a parallelization to the asymptotic approximation scheme. We finish by giving a state of the art about parallel approximation algorithms for some other problems, where the techniques used do not fit into any of the previous paradigms of parallel approximation, and which present some interesting open problems.

The Minimum Metric Traveling Salesperson Problem

Let us start by considering an important problem, the Minimum Metric Traveling Salesperson problem (MTSP). It is well known the problem is in APX. There are several heuristics to do the job. The most famous of them is the constant approximation due to Christofides [Chr76]. Moreover the problem is known to be APX-complete [PY93]. Due to the importance of the problem, quite a few heuristics have been developed for the MTSP problem. For instance, the nearest neighbor heuristics, starting at a given vertex, among all the vertices not yet visited, choose as the next vertex the one that is closest to the current vertex.

The linear programming primal-dual method has been extensively used to obtain sequential exact algorithms (see for example [Chv79], [PS82]). This algorithm keeps both a primal solution and a dual solution. When the solutions together satisfy the complementary slackness conditions, then they are mutually optimal. Otherwise either the primal solution is augmented or the dual solution is improved. The primal-dual method was originally due to Dantzing, Ford and Fulkerson [DFF56]. Unless P=NP, the primaldual method cannot be used to solve exactly in polynomial time NP-hard problems.

The primal-dual framework has been particularly useful to obtain polynomial time approximation algorithms for some NP-hard combinatorial optimization problems (see for example the forthcoming survey by Goemans and Williamson [GW96]). For those problems that can be formulated as integer programming problems, the approach works with the linear programming relaxation and its dual, and seeks for an integral extension of the linear programming solution. Furthermore the use of the combinatorial structure of each problem determines how to design the improvement steps\ and how to carry on the proof of approximation guarantee. There is no general primal-dual approximate technique; however, some approaches can be seen as producing both primal and dual feasible solutions, until some conditions are met. Those last conditions insure that the values of the primal and dual solutions are within 1 + ε of each other. As the optima of the primal and dual problems are the same, the primal and dual feasible solutions produced by the algorithm have a value within 1 + ε of optimal value.

An interesting question in graph theory is to find whether a given graph contains a vertex induced subgraph satisfying a certain property. We shall consider the special case where the property depends only on the value of a certain parameter that can take (positive) integer values. Such properties are described as weighted properties. For a given graph G = (V,E), G′ ⊆ G means that G′ is a vertex induced subgraph of G. The generic Induced Subgraph of High Weight problem (ISHW) consists in, given a graph G = (V, E), a weighted property W on the set of graphs, and an integer κ, to decide if G contains a vertex induced subgraph H such that W(H) ≥ κ. A first concrete example of the Induced Subgraph of High Weight problem is the case when W is the minimum degree of a graph. This instance of the problem is known as the High Degree Subgraph problem (HDS). Historically, this is the first problem shown to be P-complete and approximated in parallel ([AM86] and [HS87]). Another instance of the Induced Subgraph of High Weight is the case when W is the vertex (or edge) connectivity of G. These problems are known as the High Vertex Connected Subgraph problem (HVCS) (respectively the High Edge Connected Subgraph problem (HECS)). As we shall show in Chapter 8, these problems are also P-complete for any κ ≥ 3.

Anderson and Mayr studied the High Degree Subgraph problem and found that the approximability of the problem exhibits a threshold type behavior. This behavior implies that below a certain value of the absolute performance ratio, it remains P-complete, even for fixed value κ.

The approximation techniques that we consider in this chapter apply to problems that can be formulated as profit/cost problems, defined as follows: given an n × n positive matrix C and two positive vectors p and b, find an n-bit vector ƒ such that its cost C . ƒ is bounded by b and its profit p . ƒ is maximized. The value of ƒ is computed incrementally. Starting from the 0 vector, the algorithm analyzes all possible extensions incrementing one bit at a time, until it covers the n bits. Notice that the new set can have twice the size of the previous one thus leading to an exponential size set in the last step. However, we can discard some of the new assignments according to some criteria to get polynomial size sets.

Consider the interval determined by the minimum current profit and the maximum one. In the interval partitioning technique this interval is divided into small subintervals. The interval partition also gives a partition of the current set of assignment. From each class the assignment that dominates all others is selected, and the remainder discarded.

In the separation technique, the criterion used to discard possible completions insures that there are no duplicated profit values, and the profits of no three partial solutions are within a factor of each other.

The rounding/scaling technique is used to deal with problems that are hard due to the presence of large weights in the problem instance. The technique modifies the problem instance in order to produce a second instance that has no large weights, and thus can be solved efficiently.

This monograph surveys the recent developments in the field of parallel approximability to combinatorial optimization problems. The book is designed not specifically as a textbook, but as a sedimentation of a great deal of research done on this specific topic. Accordingly, we do not include a collection of exercises, but throughout the text we comment about different open research problems in the field. The monograph can easily be used as a support for advanced courses in either parallel or sequential algorithms, or for a graduate course on the topic.

In Chapter 1, we motivate the topic of parallel approximability, using an example. In the same chapter we keep the reasoning at a very intuitive level, and we survey some of the techniques and concepts that will be assumed throughout the book, like randomization and derandomization. In Chapter 2 we give a formal presentation of algorithms for the Parallel Random Access Machines model. We survey some of the known results on sequential approximability, and introduce the basic definitions and classes used in the theory of Parallel Approximability. The core of the book, Chapters 3 to 7, forms a collection of paradigms to produce parallel approximations. The word “paradigm” has a different semantic from the one used by Kuhn, in the sense that we use paradigm as a particular property or technique that can be used to give approximations in parallel for a whole class of problems. Chapter 3 presents the use of extremal graph theory, to obtain approximability to some graph problems. Chapter 4 presents parallel approximability results for profit/cost problems using the rounding, interval partitioning and separation techniques.

In this appendix we give the formal definition of the problems that have been used throughout the survey.

CIRCUIT VALUE

Instance: An encoding of a boolean circuit with n gates together with an input assignment.

Solution: The value of the output gate.

LINEAR PROGRAMMING

Instance: An integer m × n matrix A, an integer m-vector b and an integer n-vector c.

Solution: A rational n-vector x such that A x ≤ b.

Measure:cTx.

HIGH DEGREE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The minimum degree of H.

HIGH EDGE CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The edge connectivity of H.

HIGH LINKAGE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The linkage of H, defined as the maximum minimum degree of any of the subgraphs.

HIGH VERTEX CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The connectivity of H.

LOCAL MAXIMUM CUT

Instance: A graph G = (V, E) together with a partition of V.

Solution: A partition locally optimum for non-oblivious local search.

MAXIMUM ACYCLIC SUBGRAPH

Instance: A digraph G = (V, E).

Solution: Subset E′ ⊆ E such that G′ = (V, A′) is acyclic.

Measure: |E′|.

MAXIMUM 0–1 KNAPSACK

Instance: An integer b and a finite set I = {1,…,n}, for each i ∈ I an integer size Si and an integer profit pi

Solution: Subset S ⊆ I such that ∑i∈Ssi ≤ b.

Measure: ∑spi.

For some graph problems, the fact of restricting the input to planar graphs simplifies the computational complexity of the problem. However, there are some NP-complete problems that remain NP-complete even when restricted to planar graphs, for instance the Maximum Independent Set problem (see [GJ79]). We have already mentioned in the introduction that to find a constant approximation to the problem of the Maximum Independent Set for a general graph with n vertices is as difficult as to find an approximation to the problem of finding a Maximum Clique, which means that unless P=NP, the Maximum Independent Set problem cannot be approximated within n1−ε [Has96].

Baker ([Bak83], [Bak94]) took advantage of a particular way of decomposing planar graphs to produce approximation schemes for some problems that for general graphs were difficult to approximate, among them the Maximum Independent Set problem. The idea of her method is, given a problem on a planar graph, to choose a fixed κ and decompose the graph into fcouterplanar graphs (see below for the basic definitions on planar graphs), then using dynamic programming techniques obtain the exact solution to the problem for each of the κ-outerplanar graphs. For each κ, an adequate decomposition of the graph into κ-outerplanar subgraphs gives a, κ/(κ + 1) approximation to the optimal. Moreover it could be implemented in polynomial time. Taking κ = O(c log n) where c is some constant, a Polynomial Time Approximation Scheme is obtained. Using the above technique, Baker was able to produce Polynomial Time Approximation Schemes for a set of problems on planar graphs. The most significant of them is the Maximum Independent Set problem.

In this chapter we consider some problems that are non-approximable by NC algorithms unless P=NC. The basic technique used to prove non-approximability is the design of a reduction that generates instances in such a way that a gap in the value of the objective function is created.

First we concentrate on the Induced Subgraph of High Weight type problems studied in Chapter 3. Anderson and Mayr [AM86] studied this problem when the weight considered is the minimum degree of the graph. They provide a reduction from the Circuit Value problem to the High Degree Subgraph problem that creates a 1/2 gap in the weight of the so obtained instance. Kirousis, Serna and Spirakis studied this problem for two new weight functions, namely, vertex connectivity and edge connectivity, (see [SS89], [Ser90], [KSS93]). Kirousis and Thilikos analyzed the graph linkage [KT96] whose approximability presents the same kind of threshold behavior. All non-approximability results follow the same technique, that is, they create a graph, translating each circuit component or connection into a particular subgraph, in order to generate a graph that satisfies the required gap properties.

Our second result corresponds to problems that are non-approximable in NC, which means that for any e we are able to generate an instance in which an e-gap appears. Serna [Ser91] showed that the linear programming problem cannot be approximated in NC for any ratio, other non-approximable problems can be found in [SS89], [KS88], [Ser90].

To complement the non-approximability view we want to consider also the possible paralellization of heuristics used to deal with NP-hard problems.

In this chapter we provide an intuitive introduction to the topic of approximability and parallel computation. The method of approximation is one of the well established ways of coping with computationally hard optimization problems. Many important problems are known to be NP-hard, therefore assuming the plausible hypothesis that P≠NP, it would be impossible to obtain polynomial time algorithms to solve these problems.

In Chapter 2, we will give a formal definition of optimization problem, and a formal introduction to the topics of PRAM computation and approximability. For the purpose of this chapter, in an optimization problem the goal is to find a solution that maximizes or minimizes an objective function subjected to some constrains. Let us recall that in general to study the NPcompleteness of an optimization problem, we consider its decision version. The decision version of many optimization problems is NP-complete, while the optimization version is NP-hard (see for example the book by Garey and Johnson [GJ79]). To refresh the above concepts, let us consider the Maximum Cut problem (MAXCUT).

Given a graph G with a set V of n vertices and a set E of edges, the MAXCUT problem asks for a partition of V into two disjoint sets V1 and V2 that maximizes the number of edges crossing between V1 and V2. From now on through all the manuscript, all graphs have a finite number of vertices n. The foregoing statement of the MAXCUT problem is the optimization version and it is known to be NP-hard [GJ79].

In Chapter 2, we presented several complexity classes based on the approximability degree of the problems they contain: APX, PTAS, FPTAS and their parallel counterparts NCX, NCAS, FNCAS. These classes, defined in terms of degree of approximability, are known as the “computationally defined” approximation classes. We have seen that in order to show that a problem belongs to one of these classes, one can present an approximation algorithm or a reduction to a problem with known approximability properties. In this chapter we show that in some cases the approximation properties of a problem can be obtained directly from its syntactical definition. These results are based on Fagin's characterization of the class NP in terms of existential second-order logic [Fag75], which constitutes one of the most interesting connections between logic and complexity. Papadimitriou and Yannakakis discovered that Fagin's characterization can be adapted to deal with optimization problems. They defined classes of approximation problems according to their syntactical characterization [PY91]. The importance of this approach comes from the fact that approximation properties of the optimization problems can be derived from their characterization in terms of logical quantifiers. Papadimitriou and Yannakakis defined the complexity classes MaxSNP and MaxNP which contain optimization versions of many important NP problems. They showed that many MaxSNP problems are in fact complete for the class. The paradigmatic MaxSNP-complete problem is Maximum 3SAT. Recall that the Maximum 3SAT problem consists in, given a boolean formula F written in conjunctive normal form with three literals in each clause, finding a truth assignment that satisfies the maximum number of clauses.

In the previous chapter, we gave a brief introduction to the topic of parallel approximability. We keep the discussion at an intuitive level, trying to give the feeling of the main ideas behind parallel approximability. In this chapter, we are going to review in a more formal setting the basic definitions about PRAM computations and approximation that we shall use through the text. We will also introduce the tools and notation needed. In any case, this chapter will not be a deep study of these topics. There exists a large body of literature for the reader who wishes to go further in the theory of PRAM computation, among others the books by Akl [Akl89], Gibbons and Rytter [GR88], Reif [Rei93] and JáJá [JaJ92]. There are also excellent short surveys on this topic, we just mention the one by Karp and Ramachandran [KR90] and the collection of surveys from the ALCOM school in Warwick [GS93]. In a similar way, many survey papers and lecture notes have been written on the topic of approximability, among others the Doctoral Dissertation of V. Kann [Kan92] with a recent update on the appendix of problems [CK95], the lecture notes of R. Motwani [Mot92], the survey by Ausiello et al. [ACP96] which includes a survey of non-approximability methods, the recent book edited by Hochbaum [Hoc96] and a forthcoming book by Ausiello et al. [ACG+96]

The PRAM Model of Computation

We begin this section by giving a formal introduction to our basic model of computation, the Parallel Random Access Machine. A PRAM consists of a number of sequential processors, each with its own memory, working synchronously and communicating between themselves through a common shared memory.