Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem

Loading...
Thumbnail Image

Files

CS-TR-4024.ps (255.08 KB)
No. of downloads: 270
CS-TR-4024.pdf (93.33 KB)
No. of downloads: 631

Publication or External Link

Date

1999-06-08

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