Institution: Stanford University, Department of Computer Science

Title: Parallel Approximation Algorithms

Author: Mayr, Ernst W.

Date: September 1988

Abstract: Many problems of great practical importance are hard to solve computationally, at least if exact solutions are required. We survey a number of (NP- or P-complete) problems for which fast parallel approximation algorithms are known: The 0-1 knapsack problem, binpacking, the minimal makeshift problem, the list scheduling problem, greedy scheduling, and the high density subgraph problem. Algorithms for these problems are presented highlighting the underlying techniques and principles, and several types of parallel approximation schemes are exhibited.

http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1225/CS-TR-88-1225.pdf