Closed online bin packing
An optimal algorithm for the classical bin packing problem partitions (packs) a given set of items with sizes at most 1 into a smallest number of unitcapacity bins such that the sum of the sizes of the items in each bin is at most 1. Approximation algorithms for this NPhard problem are called onl...
Saved in:
Main Authors:  

Format:  Article 
Published: 
2002

Series:  Acta cybernetica
15 No. 3 
Kulcsszavak:  Számítástechnika, Kibernetika, Algoritmus 
Subjects:  
Online Access:  http://acta.bibl.uszeged.hu/12684 
Summary:  An optimal algorithm for the classical bin packing problem partitions (packs) a given set of items with sizes at most 1 into a smallest number of unitcapacity bins such that the sum of the sizes of the items in each bin is at most 1. Approximation algorithms for this NPhard problem are called online if the items are packed sequentially into bins with the bin receiving a given item being independent of the number and sizes of all items as yet unpacked. Offline algorithms plan packings assuming full (advance) knowledge of all item sizes. The closed online algorithms are intermediate: item sizes are not known in advance but the number n of items is. The uniform model, where the n item sizes are independent uniform random draws from [0,1], commands special attention in the averagecase analysis of bin packing algorithms. In this model, the expected wasted space produced by an optimal offline algorithm is Θ(√n), while that produced by an optimal online algorithm is Θ(√n log n) Surprisingly, an optimal closed online algorithm also wastes only s Θ(√n) space on the average. A proof of this last result is the principal contribution of this paper. However, we also identify a class of optimal closed algorithms, extend the main result to other probability models, and give an estimate of the hidden constant factor. 

Physical Description:  361367 
ISSN:  0324721X 