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].