Title :
A systolic-based parallel bin packing algorithm
Author :
Berkey, Judith O. ; Wang, Pearl Y.
Author_Institution :
Booz-Allen & Hamilton, Vienna, VA, USA
fDate :
7/1/1994 12:00:00 AM
Abstract :
A systolic based parallel approximation algorithm that obtains solutions to the I-D bin packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study demonstrates that the heuristic offers improved packing and execution performance over parallelizations of two well-known serial algorithms
Keywords :
computational complexity; operations research; parallel algorithms; systolic arrays; approximation algorithm; asymptotic error bound; execution performance; parallelizations; serial algorithms; systolic-based parallel bin packing algorithm; time complexity; Application software; Approximation algorithms; Computational modeling; Computer science; Concurrent computing; Operations research; Parallel algorithms; Systolic arrays;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
