# The maximum resource bin packing problem

- Description:
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, and Sanne Wøhlk.
*The maximum resource bin packing problem*.*Theoretical Computer Science*, 362:127-139, 2006. - 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 or
total size of accepted items. This paper presents results for the opposite
problems, where we would like to maximize the number of bins used or
minimize the number or total size of accepted items. We consider off-line
and on-line variants of the problems.
For the off-line variant, we require that there 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 maximum resource variant of classical bin packing.

For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms.

We study the general versions of the problems as well as the parameterized versions where there is an upper bound of 1/k on the item sizes, for some integer k.

- Copyright:
- This paper is © Elsevier B.V.
- Availability:
- Available as ps (203 KB), ps.gz (82 KB), and pdf (186 KB).

Also available at Science Direct. - Related Papers:
- The maximum resource bin packing problem (Conference Paper)
- The lazy bin packing problem (Technical Report)

See also other papers by Jens Svalgaard Kohrt.