A parallel approximation algorithm for solving one-dimensional binpacking problems

摘要

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