Approximation Algorithms and Heuristics for the Dynamic Storage
Allocation Problem
Approximation Algorithms and Heuristics for the Dynamic Storage
Allocation Problem
Files
Publication or External Link
Date
1999-06-08
Authors
Murthy, Praveen K.
Bhattacharyya, Shuvra S.
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