Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39610
Title: New approximation algorithms for some dynamic storage allocation problems
Authors: Li, S.C.
Leong, H.W. 
Quek, S.K.
Issue Date: 2004
Source: 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)
URI: http://scholarbank.nus.edu.sg/handle/10635/39610
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

101
checked on Dec 8, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.