OPT versus LOAD in dynamic storage allocation

• Published in: SIAM journal on computing 2004, Vol.33 (3), p.632-646
• Main Authors: BUCHSBAUM, Adam L, KARLOFF, Howard, KENYON, Claire, REINGOLD, Nick, THORUP, Mikkel
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Approximation; Boxes; Computer science; control theory; systems; Exact sciences and technology; Pallets; Theoretical computing
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/s0097539703423941

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= 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 $\ensuremath{\text{\it OPT}}\ge \ensuremath{\text{\it LOAD}}$; previous work showed that $\ensuremath{\text{\it OPT}}\le 3\cdot LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT=L+O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any $\epsilon > 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 $\ensuremath{\text{\it OPT}}\geq L+c(h_{\max}/L)^{1/2+\epsilon}L$, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a $(2+\epsilon)$-approximation algorithm for the general case and polynomial-time approximation schemes for several natural special cases.