Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem

Thumbnail Image
Files
CS-TR-4024.ps(255.08 KB)
No. of downloads: 269
CS-TR-4024.pdf(93.33 KB)
No. of downloads: 625
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
Notes
Rights