OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.

Saved in:

Bibliographic Details
Title:	OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.
Authors:	Buchsbaum, Adam L.¹ alb@research.att.com, Karloff, Howard¹ howard@research.att.com, Kenyon, Claire² kenyon@lix.polytechnique.fr, Reingold, Nick¹ reingold@research.att.com, Thorup, Mikkel¹ mthorup@research.att.com
Source:	SIAM Journal on Computing. 2004, Vol. 33 Issue 2, p632-646. 15p.
Subjects:	Dynamic storage allocation (Computer science), Algorithms, Polynomials, Algebra, Computer programming, Digital communications
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 ϵ > 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+ϵL, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + ϵ)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]
	Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
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 ϵ > 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+ϵL, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + ϵ)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]
ISSN:	00975397
DOI:	10.1137/S0097539703423941