Report Number: CS-TR-88-1225
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