DocumentCode
1117282
Title
A systolic-based parallel bin packing algorithm
Author
Berkey, Judith O. ; Wang, Pearl Y.
Author_Institution
Booz-Allen & Hamilton, Vienna, VA, USA
Volume
5
Issue
7
fYear
1994
fDate
7/1/1994 12:00:00 AM
Firstpage
769
Lastpage
772
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;
fLanguage
English
Journal_Title
Parallel and Distributed Systems, IEEE Transactions on
Publisher
ieee
ISSN
1045-9219
Type
jour
DOI
10.1109/71.296322
Filename
296322
Link To Document