Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
An Improved Approximation Scheme for Variable-Sized Bin Packing
verfasst von : Klaus Jansen, Stefan Kraft
Erschienen in: Mathematical Foundations of Computer Science 2012
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
The variable-sized bin packing problem (VBP) is a well-known generalization of the NP-hard bin packing problem (BP) where the items can be packed in bins of
M
given sizes. The objective is to minimize the total capacity of the bins used. We present an AFPTAS for VBP and BP with performance guarantee
$P(I) \leq (1+ \varepsilon )OPT(I) + O(\log^2(\frac{1}{\varepsilon }))$
. The additive term is much smaller than the additive term of already known AFPTAS. The running time of the algorithm is
$O( \frac{1}{\varepsilon ^6} \log\left(\frac{1}{\varepsilon }\right) + \log\left(\frac{1}{\varepsilon }\right) n)$
for bin packing and
$O(\frac{1}{\varepsilon ^{7}} \log^2\left(\frac{1}{\varepsilon }\right) + \log\left(\frac{1}{\varepsilon }\right)\left(M+n\right))$
for variable-sized bin packing, which is an improvement to previously known algorithms.