Please use this identifier to cite or link to this item: `http://hdl.handle.net/2440/83973`
Scopus Web of Science® Citations ? ?
 Type: Conference paper Title: A parallel algorithm for 2D square packing Author: Zhao, X.Shen, H. 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 Publisher Place: online Issue Date: 2013 ISBN: 9781479924189 Conference Name: International Conference on Parallel and Distributed Computing, Applications and Technologies (14th : 2013 : Taipei, Taiwan) Statement ofResponsibility: 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. [23] 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 RMID: 0020137370 DOI: 10.1109/PDCAT.2013.35 Description (link): http://pdcat13.csie.ntust.edu.tw/ Published version: http://pdcat13.csie.ntust.edu.tw/download/papers/P10018.pdf Appears in Collections: Computer Science publications

Files in This Item:
There are no files associated with this item.