STOC Conference 2003 Conference Paper
OPT versus LOAD in dynamic storage allocation
- Adam L. Buchsbaum
- Howard J. Karloff
- Claire Mathieu
- Nick Reingold
- Mikkel Thorup
DYNAMIC STORAGE ALLOCATION is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L=LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT≥LOAD ; previous work showed that OPT≤ 3• LOAD . We continue the study of the relationship between OPT and LOAD , proving that OPT=L+O((h max /L) 1/7 )L , where h max is the maximum job height. Conversely, we prove that for any ε>0 , there exists a c>0 such that for all sufficiently large integers h max , there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height h max , maximum load at most L , and OPT≥ L+c(h max /L) 1/2+ε L , for infinitely many integers L . En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.