TY - GEN

T1 - A parallel algorithm for 2D square packing

AU - Zhao, Xiaofan

AU - Shen, Hong

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2014/9/18

Y1 - 2014/9/18

N2 - 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 algorithmA for an instance Iof 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.

AB - 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 algorithmA for an instance Iof 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.

KW - approximation algorithm

KW - parallel bin packing

KW - two-dimensional square packing

KW - upper bound

UR - http://www.scopus.com/inward/record.url?scp=84908009853&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2013.35

DO - 10.1109/PDCAT.2013.35

M3 - Conference contribution

AN - SCOPUS:84908009853

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 179

EP - 183

BT - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

A2 - Horng, Shi-Jinn

PB - IEEE Computer Society

T2 - 14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2013

Y2 - 16 December 2013 through 18 December 2013

ER -