| Article ID: | iaor20117038 |
| Volume: | 36 |
| Issue: | 3 |
| Start Page Number: | 261 |
| End Page Number: | 293 |
| Publication Date: | Jul 2003 |
| Journal: | Algorithmica |
| Authors: | Seiden , van Stee |
| Keywords: | bin packing |
New upper and lower bounds are presented for a multidimensional generalization of bin packing called box packing. Several variants of this problem, including bounded space box packing, square packing, variable‐sized box packing and resource augmented box packing are also studied. The main results, stated for d=2 , are as follows: a new upper bound of 2.66013 for online box packing, a new 14/9 + ϵ polynomial time offline approximation algorithm for square packing, a new upper bound of 2.43828 for online square packing, a new lower bound of 1.62176 for online square packing, a new lower bound of 2.28229 for bounded space online square packing and a new upper bound of 2.32571 for online two‐sized box packing.