On-line bin packing-A restricted survey

On-line bin packing-A restricted survey

0.00 Avg rating0 Votes
Article ID: iaor19961641
Country: Germany
Volume: 42
Issue: 1
Start Page Number: 25
End Page Number: 45
Publication Date: Jul 1995
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: ,
Keywords: combinatorial analysis
Abstract:

In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970’s, the authors survey-from the worst case point of view-the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bounds on worst case ratios and related results.

Reviews

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