It is sometimes computationally infeasible (even with a parallel computer) to obtain exact answers to some combinatorial optimization problems. Instead, a near-optimal solution is computed using an...

It is sometimes computationally infeasible (even with a parallel computer) to obtain exact answers to some combinatorial optimization problems. Instead, a near-optimal solution is computed using an approximation method. One such method is known as local neighborhood search. Let f be a combinatorial function that is to be minimized, say. We begin by computing the value of f at a randomly chosen point. The neighbors of that point are then examined and the value of f computed for each new point. Each time a point reduces the value of the function, we move to that point. This continues until no further improvement can be obtained. The point reached is labeled a local minimum. The entire process is repeated several times, each time from a new random point. Finally, a global minimum is computed from all local minima thus obtained. This is the approximate answer. Discuss various ways for obtaining a parallel version of this method that runs on an MIMD computer.