{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:32Z","timestamp":1787322872553,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1996,2]]},"abstract":"<jats:p>This paper is concerned with on-line storage allocation to processes in a dynamic environment. This problem has been extensively studied in the past. We provide a new, tighter bound for the competitive ratio of the well-known First Fit algorithm. This bound is obtained by considering a new parameter, namely the maximum number of concurrent active processes. We observe that this bound is also a lower bound on the competitive ratio of any deterministic on-line algorithm. Our second contribution is an on-line allocation algorithm that uses coloring techniques. We show that the competitive ratio of this algorithm is the same as that of First Fit. Furthermore, we indicate that this algorithm may be advantageous in certain applications. Our third contribution is to analyze the performance of randomized algorithms for this problem. We obtain lower bounds on the competitive ratio that are close to the best deterministic upper bounds.<\/jats:p>","DOI":"10.1137\/s089548019325647x","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:08:45Z","timestamp":1109146125000},"page":"155-166","source":"Crossref","is-referenced-by-count":20,"title":["Tight Bounds for Dynamic Storage Allocation"],"prefix":"10.1137","volume":"9","author":[{"given":"Michael G.","family":"Luby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Orda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/65979.65981"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/1025074"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-4338-4_3"},{"key":"R6","unstructured":"D. Detlefs, A. Dosser, B. Zorn, Memory Allocation Costs in Large C and C++ Programs, Technical Report, CU-CS-665-93, University of Colorado, Boulder, 1993"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1063\/1.3034322"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"R9","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0401048"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90011-P"},{"key":"R12","volume-title":"Fundamental Algorithms, Vol. 1","author":"Knuth D. E.","year":"1973"},{"key":"R13","unstructured":"M. G. Luby, J. Naor, A. Orda, Tight bounds for dynamic storage allocation, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, 1994, 724\u20137320871.68061"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. S. Manasse, L. A. McGeoch, D. D. Sleator, Competitive algorithms for on-line problems, Proc. 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, 1988, 322\u20133330796.68042","DOI":"10.1145\/62212.62243"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/321650.321658"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/321832.321846"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.3.242"},{"key":"R18","volume-title":"Data Structures Techniques","author":"Standish T. A.","year":"1980"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.2307\/2319522"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/51607.51619"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao, Probabilistic computations: toward a unified measure of complexity (extended abstract), 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Comput. Sci., Long Beach, Calif., 1977, 222\u201322758:8500","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S089548019325647X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:30:44Z","timestamp":1787319044000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S089548019325647X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,2]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,2]]}},"alternative-id":["10.1137\/S089548019325647X"],"URL":"https:\/\/doi.org\/10.1137\/s089548019325647x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,2]]}}}