Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem
| dc.contributor.author | Murthy, Praveen K. | en_US |
| dc.contributor.author | Bhattacharyya, Shuvra S. | en_US |
| dc.date.accessioned | 2004-05-31T22:57:48Z | |
| dc.date.available | 2004-05-31T22:57:48Z | |
| dc.date.created | 1999-06 | en_US |
| dc.date.issued | 1999-06-08 | en_US |
| dc.description.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 | en_US |
| dc.format.extent | 261201 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1013 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4024 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-99-31 | en_US |
| dc.title | Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem | en_US |
| dc.type | Technical Report | en_US |