Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Approximation Schemes for Packing Splittable Items with Cardinality Constraints
verfasst von : Leah Epstein, Rob van Stee
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of items must be packed into as few bins as possible. Items may be split, but each bin may contain at most
k
(parts of) items, where
k
is some fixed constant. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. We close this problem by providing a polynomial-time approximation scheme for it. We first present a scheme for the case
k
= 2 and then for the general case of constant
k
.
Additionally, we present
dual
approximation schemes for
k
= 2 and constant
k
. Thus we show that for any
ε
> 0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1 +
ε
.