- The Maximum Resource Bin Packing Problem.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, and Sanne Wøhlk.
In 15th International Symposium on Fundamentals of Computation Theory (FCT), volume 3623 of Lecture Notes in Computer Science, pages 397-408. Springer, 2005.
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
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 final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.