ABSTRACT
This chapter explores some approximation algorithms for the dynamic storage allocation (DSA) problem; and an approximation algorithm which is simply a heuristic with a performance guarantee. The "dynamic" in DSA refers to the fact that many times the problem is on-line in nature: the allocation has to be performed as the intervals come and go. For synchronous dataflow scheduling, the problem is not really "dynamic" since the lifetimes and sizes of all the arrays that need to be allocated are known at compile time; thus, the problem should perhaps be called static storage allocation. The approximation algorithm of for DSA is based on a simultaneous recursive formulation that actually colors an exponentially bigger graph F than the weighted interval graph. First fit is the well-known algorithm that performs allocation for an enumerated instance by assigning the smallest feasible location to each interval in the order they appear in the enumerated instance.
