Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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((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.

REFERENCES

• 1: M. Chrobak and M. Slusarek, "On Some Packing Problem Related to Dynamic Storage Allocation," RAIRO Informatique Theorique et Applications 22 (1988), 487--499.
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 3: Jordan Gergov, Approximation Algorithms for Dynamic Storage Allocations, Proceedings of the Fourth Annual European Symposium on Algorithms, p.52-61, September 25-27, 1996
• 4: Jordan Gergov, Algorithms for compile-time memory optimization, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.907-908, January 17-19, 1999, Baltimore, Maryland, United States
• 5: H. A. Kierstead, The linearity of first-fit coloring of interval graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.526-530, Nov. 1988 [doi>10.1137/0401048]
• 6: H. A. Kierstead, A polynomial time approximation algorithm for Dynamic Storage Allocation, Discrete Mathematics, v.87 n.2-3, p.231-237, Jan. 31 1991
• 7: D. R. Woodall, "Problem No. 4," Proc. British Combinatorial Conference (1973), London Mathematical Society Lecture Notes Series 13, Cambridge University Press, 1974, 202.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, dynamic storage allocation, polynomial time approximation schemes