The lazy bin packing problem

Description:

Joan Boyar, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, and Sanne Wøhlk. The lazy bin packing problem. Technical Report PP-2004-06, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, 2004.

Abstract:

Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number of accepted items or accepted volume. This paper presents results for the opposite problems, where we want to maximize the number of bins used or minimize the number of accepted items or the accepted volume.

For the off-line variant, we require that there must be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing.

For the on-line variant, we define two different bin packing problems. In the case where the number of available bins is fixed, no on-line algorithm is competitive. For an unlimited number of bins, we find the competitive ratio of various natural algorithms.

Availability:

Available as ps (306 KB), ps.gz (154 KB), and pdf (175 KB).
Also available at the DMF Preprint Server.

Related Papers:

• The maximum resource bin packing problem (Journal Paper)
• The maximum resource bin packing problem (Conference Paper)