A parallel approximation algorithm for solving one-dimensional bin packing problems

Describes a parallel approximation algorithm that can be used to obtain solutions to the one-dimensional bin packing problem: a list L of n items with sizes in the interval [0,1] is to be packed into a minimum number of unit-size bins. The algorithm is based on a systolic model of computation and packs items into one-dimensional bins by dividing L into ten subsets of pieces that are processed concurrently. It is shown that this algorithm has a worst case asymptotic error bound of 1.5 and a time complexity of Θ(n). The algorithm has also been implemented on an Inmos transputer array and execution results are reviewed to show how the method performs in practice