TIGHT BOUNDS FOR DYNAMIC STORAGE-ALLOCATION

This paper is concerned with on-line storage allocation to processes i n 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 conside ring a new parameter, namely the maximum number of concurrent active p rocesses. We observe that this bound is also a lower bound on the comp etitive ratio of any deterministic on-line algorithm. Our second contr ibution is an on-line allocation algorithm that uses coloring techniqu es. We show that the competitive ratio of this algorithm is the same a s 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 bes t deterministic upper bounds.