Approximation Algorithms and Heuristics for the Dynamic Storage
Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem
Publication or External Link
Murthy, Praveen K.
Bhattacharyya, Shuvra S.
In this report, we look at the problem of packing a number of arrays in memory efficiently. This is known as the dynamic storage allocation problem (DSA) and it is known to be NP-complete. We develop some simple, polynomial-time approximation algorithms with the best of them achieving a bound of 4 for a sub-class of DSA instances. We report on an extensive experimental study on the FirstFit heuristic and show that the average-case performance on random instances is within 7% of the optimal value. Also cross-referenced as UMIACS-TR-99-31