Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A storage-size selection problem
Friesen D., Langston M. Information Processing Letters18 (5):295-296,1984.Type:Article
Date Reviewed: Feb 1 1985

This paper discusses a variation of the bin-packing problem in which we want to not only minimize the wasted space, but also choose the best bin :9I ; and the best packing into bins of this size to minimize wasted space. This problem reflects a memory allocation problem. Clearly this problem is NP-hard, as the authors point out. The authors later make this important observation: If a bin-packing algorithm A can guarantee a worst-case ratio R for the usual bin-packing problem, then an iterated version, A* can be used to achieve a bound as close to R as desired for this problem. The nmber of iterations is log :9I , for hich the base of the logarithm is :9I. It should be pointed out that the number of iterations is a function of :9I closeness to R. The paper presents a new problem and is clearly written.

Reviewer:  M. S. Krishnamoorthy Review #: CR108803
Bookmark and Share
 
Sequencing And Scheduling (F.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Sequencing And Scheduling": Date
Early stopping in Byzantine agreement
Dolev D., Reischuk R., Strong H. Journal of the ACM 31(4): 720-741, 1984. Type: Article
Nov 1 1991
Scheduling independent 2-processor tasks to minimize schedule length
Blazewicz J., Weglarz J., Drabowski M. Information Processing Letters 18(5): 267-273, 1984. Type: Article
Jan 1 1985
Performance of heuristics for a computer resource allocation problem
Langston M. SIAM Journal on Algebraic and Discrete Methods 5(2): 154-161, 1984. Type: Article
Mar 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy