- The Maximum Resource Bin Packing Problem.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten M. Pedersen, and Sanne Wøhlk.
Theoretical Computer Science, 362(1-3):127-139, 2006.
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.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The publication is available from ScienceDirect.
open access (158 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.