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.