A storage-size selection problem

DOI10.1016/0020-0190(84)90010-3MaRDI QIDQ795502zbMATH OpenOpenAlexFDO

Authors Donald K. Friesen, Michael A. Langston

Publication date 1984

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(84)90010-3

zbMATH Keywords

approximation algorithmsbin packingworst-case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

In the usual bin packing problem one is given a set of pieces and a bin size and the objective is to minimize the number of bins used to pack the pieces. This is equivalent to finding a packing with the least wasted space. This paper investigates the question of what can be done if, in addition, one is allowed to choose the bin size (which must be the same for all bins). How should one compute the best bin size, \(\alpha\), and the best packing into bins of this size to minimize wasted space?

Recommendations

• Variable Sized Bin Packing
• Optimal Bin Packing with Items of Random Sizes II
• Online variable-sized bin packing
• Probabilistic behaviour of optimal bin-packing solutions
• Algorithms for the variable sized bin packing problem

Cites work

• Fast algorithms for bin packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(6)

• A 71/60 theorem for bin packing
• Online variable-sized bin packing
• Optimal allocation of storage space
• Heuristic methods and applications: A categorized survey
• An on-line algorithm for variable-sized bin packing
• Variable-sized object packing and its applications to instruction cache design

This page was built for publication: A storage-size selection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795502)