Abstract
The offline dynamic storage allocation (DSA) problem has recently received some renewed attention and several new results have been reported. The problem is NP-complete and the best known result for the offline DSA is a polynomial time 3-approximation algorithm [Gerg99]. Better ratios have been reported for special cases if restrictions are placed on the allowable sizes of the blocks [Gerg96,MuBh99]. In this paper, we present new techniques for solving special cases with blocks of restricted sizes and we obtain better approximation ratios for them. We first obtain results for small instances which are then used to solve the more general cases. Our main results are (i) a 4/3-approximation algorithm when the maximum block size h=2 (previous best was 3/2); and (ii) a 1.7-approximation algorithm for the case h=3 (previous best was 1\(\frac{11}{12}\)).
This work was supported in part by the National University of Singapore under Grant R252-000-128-112.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: Computers and Intractability – A guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gergov, J.: Approximation algorithms for dynamic storage allocation. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 52–61. Springer, Heidelberg (1996)
Gergov, J.: Algorithms for Compile-Time Memory Optimization. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 907–908 (1999)
Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Disc. Math. 1, 526–530 (1988)
Kierstead, H.A.: A polynomial time approximation algorithm for Dynamic Storage Allocation. Discrete Mathematics 88, 231–237 (1991)
Knuth, D.E.: Fundamental Algorithms: The art of computer programming, vol. 1. Addison-Wesley Pub., Reading (1973)
Li, S.C.: Algorithms for Berth Allocation Problem, M.Sc Thesis, Department of Computer Science, National University of Singapore (2002)
Ludy, M.G., Naor, J., Orda, A.: Tight Bounds for Dynamic Storage Allocation. J. ACM 12, 491–499 (1974)
Murthy, P.K., Bhattacharyya, S.S.: Approximation algorithms and heuristics for dynamic storage allocation problem. UMIACS TR-99-31, University of Maryland, College Park (1999)
Robson, J.M.: Bounds for some functions concerning dynamic storage allocation. Journal of the ACM 21(3), 491–499 (1974)
Robson, J.M.: Worst base fragmentation of first fit and best fit storage allocation strategies. Computer Journal 20, 242–244 (1977)
Slusarek, M.: A Coloring Algorithm for Interval Graphs. In: Kreczmar, A., Mirkowska, G. (eds.) MFCS 1989. LNCS, vol. 379, pp. 471–480. Springer, Heidelberg (1989)
Wilson, P.R., Johnstone, M.S., Neely, M., Boles, D.: Dynamic storage allocation: A survey and critical review. In: Baker, H.G. (ed.) IWMM-GIAE 1995. LNCS, vol. 986. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, S.C., Leong, H.W., Quek, S.K. (2004). New Approximation Algorithms for Some Dynamic Storage Allocation Problems. In: Chwa, KY., Munro, J.I.J. (eds) Computing and Combinatorics. COCOON 2004. Lecture Notes in Computer Science, vol 3106. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27798-9_37
Download citation
DOI: https://doi.org/10.1007/978-3-540-27798-9_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22856-1
Online ISBN: 978-3-540-27798-9
eBook Packages: Springer Book Archive