Multidimensional Cube Packing

We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimensional cubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L into the minimum number of bins. We present two approximations algorithms for d-CPP, for fixed d. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to 2 - 1/2d. The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to 2 - (2/3)d. To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, and are the first results with bounds that are not exponential in the dimension.7110113Coppersmith, D., Raghavan, P., Multidimensional on-line bin packing: Algorithms and worst-case analysis (1989) Oper. Res. Lett., 8 (1), pp. 17-20Karmarkar, N., Karp, R.M., An efficient approximation scheme for the one dimensional bin packing problem (1982) Proc. 23rd Ann. Symp. on Foundations of Computer Science, pp. 312-320. , IEEE Computer Society, Los AngelesDe La Vega, W.F., Luecker, G.S., Bin packing can be solved within 1 + ε in linear time (1981) Combinatorica, 1 (4), pp. 349-355Ferreira, C.E., Miyazawa, F.K., Wakabayashi, Y., Packing of squares into squares (1999) Pesquisa Operacional, 19 (2), pp. 223-237Chung, F.R.K., Garey, M.R., Johnson, D.S., On packing two-dimensional bins (1982) SIAM J. Algebraic Discrete Methods, 3, pp. 66-76Miyazawa, F.K., Wakabayashi, Y., Cube packing (2000) Lecture Notes in Computer Science, 1776, pp. 58-67. , Proc. 4th Latin American Theoretical INformatics., Springer-Verlag, Punta del Este, UruguayLi, K., Cheng, K.-H., (1990) A Generalized Harmonic Algorithm for On-line Multidimensional Bin Packing, , TR UH-CS-90-2, University of Houston JanuaryCsirik, J., Van Vliet, A., An on-line algorithm for multidimensional bin packing (1993) Operations Research Letters, 13, pp. 149-158Meir, A., Moser, L., On packing of squares and cubes (1968) J. Combinatorial Theory Ser. A, 5, pp. 116-127Miyazawa, F.K., Wakabayashi, Y., Approximation algorithms for the orthogonal z-oriented 3-D packing problem (2000) SIAM J. Computing, 29 (3), pp. 1008-102