Please use this identifier to cite or link to this item:
|Title:||New approximation algorithms for some dynamic storage allocation problems|
|Citation:||Li, S.C.,Leong, H.W.,Quek, S.K. (2004). New approximation algorithms for some dynamic storage allocation problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3106 : 339-348. ScholarBank@NUS Repository.|
|Abstract:||The offline dynamic storage allocation (DSA) problem has recently received some renewed attention and several new results have been reported. The problem is NP-complete and the best known result for the offline DSA is a polynomial time 3-approximation algorithm [Gerg99]. Better ratios have been reported for special cases if restrictions are placed on the allowable sizes of the blocks [Gerg96,MuBh99]. In this paper, we present new techniques for solving special cases with blocks of restricted sizes and we obtain better approximation ratios for them. We first obtain results for small instances which are then used to solve the more general cases. Our main results are (i) a 4/3-approximation algorithm when the maximum block size h=2 (previous best was 3/2); and (ii) a 1.7-approximation algorithm for the case h=3 (previous best was 1 11/12). © Springer-Verlag Berlin Heidelberg 2004.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 8, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.