New Bounds for Multidimensional Packing |
| |
| Authors: | Seiden and van Stee |
| |
| Affiliation: | (1) Department of Computer Science, 298 Coates Hall, Louisiana State University, Baton Rouge, LA 70803, USA., US;(2) Institut f{ü}r Informatik, Albert-Ludwigs-Universit{?}t, Georges-K{?}hler-Allee, 79110 Freiburg, Germany. vanstee@uni-freiburg.de., DE |
| |
| Abstract: | Abstract. 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. |
| |
| Keywords: | , Bin packing, Box packing, Approximation algorithms, Online algorithms, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
