Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||A parallel algorithm for 2D square packing|
|Citation:||Proceedings of the 14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT'13, 2013 / pp.1-5|
|Publisher:||IEEE Computer Society|
|Conference Name:||International Conference on Parallel and Distributed Computing, Applications and Technologies (14th : 2013 : Taipei, Taiwan)|
|Xiaofan Zhao and Hong Shen|
|Abstract:||We focus on the parallelization of two-dimensional square packing problem. In square packing problem, a list of square items need to be packed into a minimum number of unit square bins. All square items have side length smaller than or equal to 1 which is also the side length of each unit square bin. The total area of items that has been packed into one bin cannot exceed 1. Using the idea of harmonic, some squares can be put into the same bin without exceeding the bin limitation of side length 1 We try to concurrently pack all the corresponding squares into one bin by a parallel systerm of computation processing. A 9=4-worst case asymptotic error bound algorithm with time complexity (n) is showed. Let OPT(I) and A(I) denote, respectively, the cost of an optimal solution and the cost produced by an approximation algorithm A for an instance I of the square packing problem. The best upper bound of on-line square packing to date is 2.1439 proved by Han et al.  by using complexity weighting functions. However the upper bound of our parallel algorithm is a litter worse than Han’s algorithm, the analysis of our algorithm is more simple and the time complexity is improved. Han’s algorithm needs O(nlogn) time, while our method only needs (n) time.|
|Keywords:||parallel bin packing; two-dimensional square packing; upper bound; approximation algorithm|
|Rights:||Copyright status unknown|
|Appears in Collections:||Computer Science publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.