Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation algorithms for dynamic storage allocation

  • Conference paper
  • First Online:
Algorithms — ESA '96 (ESA 1996)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1136))

Included in the following conference series:

Abstract

We present a new O(n log n)-time 5-approximation algorithm for the NP-hard dynamic storage allocation problem (DSA). The two previous approximation algorithms for DSA are based on on-line coloring of interval graphs and have approximation ratios of 6 and 80 [6, 7, 16]. Our result gives an affirmative answer to the important open question of whether the approximation ratio of DSA can be improved below the bound implied by on-line coloring of interval graphs [7, 16]. Our approach is based on the novel concept of a 2-allocation and on the design of an efficient transformation of a 2-allocation to an at most 5/2 times larger memory allocation.

For the NP-hard variant of DSA with only two sizes of blocks allowed, we give a simpler 2-approximation algorithm. Further, by means of a tighter analysis of the widely used First Fit strategy, we show how the competitive ratio of on-line DSA can be improved to Θ(max{1, log(nk/M)}) where M, k, and n are upper bounds on the maximum number of simultaneously occupied cells, the maximum number of blocks simultaneously in the storage, and the maximum size of a block.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data structures and algorithms, Addison-Wesley, 1983.

    Google Scholar 

  2. M. Chrobak, M. Slusarek, On some packing problem related to dynamic storage allocation, RAIRO Informatique Theorique et Applications 22 (1988), pp. 487–499.

    Google Scholar 

  3. D. Detlefs, A. Dosser, and B. Zorn, Memory allocation costs in large C and C++ programs, Software: Practice and Experience, 24 (6), 1994, pp. 527–542.

    Google Scholar 

  4. M.R. Garey and D.S. Johnson, Computers and Intractability—A Guide to the Theory of NP-Completeness, Freeman, (1979).

    Google Scholar 

  5. H.A. Kierstead and W.T. Trotter, An extremal problem in recursive combinatorics, Congr. Numerantium 33 (1981), pp. 143–153.

    Google Scholar 

  6. H.A. Kierstead, The linearity of first-fit coloring of interval graphs, SIAM J. Disc. Math. 1 (1988), pp. 526–530.

    Google Scholar 

  7. H.A. Kierstead, A polynomial time approximation algorithm for Dynamic Storage Allocation, Discrete Mathematics 88 (1991), pp. 231–237.

    Google Scholar 

  8. K. Knowlton, A fast storage allocator, Comm. of ACM, Vol. 8, 1965, pp. 623–625.

    Google Scholar 

  9. D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental algorithms, 2nd Edition, Addison-Wesley, Reading, MA, 1973.

    Google Scholar 

  10. S. Krogdahl, A dynamic storage allocation problem, Information Processing Letters, 2, 1973, pp. 96–99.

    Google Scholar 

  11. M.G. Luby, J. Naor, and A. Orda, Tight bounds for dynamic storage allocation, in Proc. 5th Annual ACM-SIAM Symp. on Discrete Algorithms, 1994, pp. 724–732.

    Google Scholar 

  12. J.M. Robson, An estimate of the store size necessary for dynamic storage allocation, J. ACM, Vol. 18, 1971, pp. 416–423.

    Google Scholar 

  13. J.M. Robson, Bounds for some functions concerning dynamic storage allocation, J. ACM, Vol. 12, 1974, pp. 491–499.

    Google Scholar 

  14. J.M. Robson, Worst case fragmentation of first fit and best fit storage allocation strategies, Computer Journal, Vol. 20, 1977, pp. 242–244.

    Google Scholar 

  15. M. Slusarek, NP-Completeness of Storage Allocation, Jagiellonian U. Scientific Papers, s. Informatics 3 (1987), pp. 7–18.

    Google Scholar 

  16. M. Slusarek, A coloring algorithm for interval graphs, in Proc. 14th Mathematical Foundations of Computer Science (1989), LNCS 379, Springer, pp. 471–480.

    Google Scholar 

  17. T.A. Standish, Data structures techniques, Addison-Wesley Publishing Company, 1980.

    Google Scholar 

  18. D.R. Woodall, Problem No. 4, in Proc. British Combinatorial Conference (1973), London Math. Soc. Lecture Notes Series 13, Cambridge University Press, 1974, p. 202

    Google Scholar 

  19. D.R. Woodall, The bay restaurant—a linear storage problem, American Mathematical Monthly, Vol. 81, 1974, pp. 240–246.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Max-Planck-Institut für Informatik, D-66123, Saarbrücken, Germany

    Jordan Gergov

Authors
  1. Jordan Gergov
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Josep Diaz Maria Serna

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gergov, J. (1996). Approximation algorithms for dynamic storage allocation. In: Diaz, J., Serna, M. (eds) Algorithms — ESA '96. ESA 1996. Lecture Notes in Computer Science, vol 1136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61680-2_46

Download citation

  • DOI: https://doi.org/10.1007/3-540-61680-2_46

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61680-1

  • Online ISBN: 978-3-540-70667-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation