Parallel approximation algorithms for bin packing

AbstractWe study the parallel complexity of polynomial heuristics for the bin packing problem. We show that some well-known (and simple) methods like first-fit-decreasing areP-complete, and it is hence very unlikely that they can be efficiently parallelized. On the other hand, we exhibit an optimalNCalgorithm that achieves the same performance bound as does FFD. Finally, we discuss parallelization of polynomial approximation algorithms for bin packing based on discretization