TY - JOUR
T1 - Parallel approximation algorithms for bin packing
AU - Anderson, Richard J.
AU - Mayr, Ernst W.
AU - Warmuth, Manfred K.
PY - 1989/9
Y1 - 1989/9
N2 - We 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 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.
AB - We 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 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.
UR - http://www.scopus.com/inward/record.url?scp=0024738301&partnerID=8YFLogxK
U2 - 10.1016/0890-5401(89)90003-5
DO - 10.1016/0890-5401(89)90003-5
M3 - Article
AN - SCOPUS:0024738301
SN - 0890-5401
VL - 82
SP - 262
EP - 277
JO - Information and Computation
JF - Information and Computation
IS - 3
ER -