7 - Further Parallel Approximations

Summary

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.