We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Online square and cube packing.
- Authors
Epstein, Leah; Stee, Rob
- Abstract
In online square packing, squares of different sizes arrive online and need to be packed into unit squares which are called bins. The goal is to minimize the number of bins used. Online cube packing is defined analogously. We show an upper bound of 2.2697 and a lower bound of 1.6406 for online square packing, and an upper bound of 2.9421 and a lower bound of 1.6680 for online cube packing. The upper bound for squares can be further reduced to 2.24437 using a computer proof. These results improve on the previously known results for the two problems. We also show improved lower bounds for higher dimensions.
- Subjects
COMPUTERS; COMPUTER systems; PACKAGING; BINS; CUBES; SQUARE
- Publication
Acta Informatica, 2005, Vol 41, Issue 9, p595
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-005-0169-z