Back to Search
Start Over
OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.
- Source :
-
SIAM Journal on Computing . 2004, Vol. 33 Issue 2, p632-646. 15p. - Publication Year :
- 2004
-
Abstract
- 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((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any &epsiv; > 0, there exists a c > 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+&epsiv;L, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + &epsiv;)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 33
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 13266085
- Full Text :
- https://doi.org/10.1137/S0097539703423941