An Improved Approximation Scheme for Variable-Sized Bin Packing

Abstract 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.

Authors

• Klaus Jansen
• Stefan Erich Julius Kraft

Keywords

No keywords are indexed for this paper.