Further Parallel Approximations
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{daz1997further,
author = {Josep Dı́az and Marı́a Serna and Paul G. Spirakis and Jacobo Torán},
title = {{Further Parallel Approximations}},
booktitle = {Cambridge},
year = {1997},
doi = {10.1017/cbo9780511666407.008},
}Loading related content...