Approximation Algorithms and Heuristics for the Dynamic Storage
Allocation Problem
Approximation Algorithms and Heuristics for the Dynamic Storage
Allocation Problem
Loading...
Files
Publication or External Link
Date
Advisor
Citation
DRUM DOI
Abstract
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