Electronic Resource
Springer
Acta informatica
9 (1978), S. 263-271
ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary We consider a variant of the classical one-dimensional bin-packing problem: The number of bins is fixed and the object is to maximize the number of pieces packed from some given set. Both problems have applications in processor and storage allocation in computer systems in addition to a broad application in operations research. It can easily be shown that both problems are NP-complete; our approach will be to propose and analyze very fast heuristics. We consider a class of algorithms and bound the performance of an arbitrary algorithm in that class. Finally we propose an algorithm, the first-fit-increasing algorithm, and analyze its running time and relative performance.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00288885
Permalink
|
Location |
Call Number |
Expected |
Availability |