OPT versus LOAD in dynamic storage allocation

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.

Authors

• Adam L. Buchsbaum
• Howard J. Karloff
• Claire Mathieu
• Nick Reingold
• Mikkel Thorup

Keywords

• approximation algorithms
• dynamic storage allocation
• polynomial time approximation schemes