Report Number: CS-TR-88-1200
Institution: Stanford University, Department of Computer Science
Title: Parallel Approximation Algorithms for Bin Packing
Author: Anderson, R. J.
Author: Mayr, E. W.
Author: Warmuth, M. K.
Date: March 1988
Abstract: We study the parallel complexity of polynomial heuristics for the bin packing problem. We show that some well-known (and simple) moethods like first-fit- decreasing are P-complete, and it is hence very unlikely that they can be efficiently parallelized. On the other hand, we exhibit an optimal NC algorithm that achieves the same performance bound as does FFD. Finally, we discuss parallelization of polynomial approximation algorithms for bin packing based on discretization.
http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1200/CS-TR-88-1200.pdf