Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
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)
Editor: Horng, S.J.
Statement of
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
DOI: 10.1109/PDCAT.2013.35
Description (link):
Published version:
Appears in Collections:Aurora harvest
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.