Parametric on-line algorithms for packing rectangles and boxes
We present approximation algorithms for the following problems: the two-dimensional bin packing (2BP), the three-dimensional packing problem (TPP) and the container packing problem (3BP). We consider the special case in which the items to be packed are small and must be packed on-line. We say an item is small if each of its dimension is at most 1/m of the respective dimension of the recipient, where m is an integer greater than 1. These problems are denoted by 2BPm, TPPm and 3BPm, and the performance of the algorithms are given in terms of the parameter m. To our knowledge, the parametric on-line algorithms we present here have the best so far achieved asymptotic performance bounds for these problems. For 2BPm and TPPm we present algorithms with performance bound close to (m+2)/m+1/(m+1)2, and for 3BPm we describe an algorithm with performance bound close to (m+3)/m+2/m2+1/(m+1)2. For m=2 (respectively m=3) these bounds are 2.112 and 3.112 (respectively 1.73 and 2.285). The results on 2BPm and 3BPm extend the results on multidimensional on-line packing presented by Coppersmith and Raghavan [Oper. Res. Lett. 8(1) (1989) 17]. The result on TPPm improves the bound (m+1)/(m?1) due to Li and Cheng [SIAM J. Comput. 19 (1990) 847]. All these algorithms can be implemented to run in O(nlogn) time, where n is the number of items to be packed.
packing approximation algorithms three-dimensional packing on-line packing parametric packing