On-line maximizing the number of items packed in variable-sized bins

On-line maximizing the number of items packed in variable-sized bins

0.00 Avg rating0 Votes
Article ID: iaor20043721
Country: Hungary
Volume: 16
Issue: 1
Start Page Number: 57
End Page Number: 66
Publication Date: Jan 2003
Journal: Acta Cybernetica
Authors: ,
Keywords: programming: integer
Abstract:

We study on-line bin packing problem. A fixed number of n. of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3, and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/(2n−1).

Reviews

Required fields are marked *. Your email address will not be published.