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