An Improved Approximation Scheme for Variable-Sized Bin Packing

It should be noted that p(a ₁)<p(a ₂) does not always imply q(a ₁)≤q(a ₂). Let p(a ₁)=2 ^k+1 T and p(a ₂)=(2 ^k+1+2 ^k+1 δ)T for small enough δ>0 such that \(q(a_{1}) = \left \lfloor {\frac {4}{\varepsilon }}\right \rfloor 2^{k} > q(a_{2}) = \left \lfloor {\frac {2 + 2 \delta }{\varepsilon }}\right \rfloor 2^{k+1} = \left \lfloor {\frac {2}{\varepsilon }}\right \rfloor 2^{k+1}\), i.e. \(\left \lfloor {\frac {4}{\varepsilon }}\right \rfloor > 2 \left \lfloor {\frac {2}{\varepsilon }}\right \rfloor \). Values ε>0 for which the latter condition holds can be easily found. However, the possible non-monotonicity does not change the results and proofs in this subsection because the monotonicity is not used. In fact, this subsection uses another order (see e.g. Lemma 40) where \(q_{1}, \ldots , q_{j^{\prime }}\) are the scaled profits in decreasing order for the largest interval (2 ^k T _b ,2 ^k+1 T _b ], the items \(q_{j^{\prime }+1}, \ldots , q_{j^{\prime \prime }}\) are the scaled profits in decreasing order for (2 ^k−1 T _b ,2 ^k T _b ] etc. For simplicity, we assume here that this order corresponds to sorting the q _j in non-increasing order (which is true if the scaling monotonicity holds). Moreover, the scaling monotonicity can be guaranteed by assuming without loss of generality that \(\varepsilon = \frac {1}{2^{\kappa }}\) for \(\kappa \in \mathbb {N}\).

The authors have been able to improve the running time of an FPTAS for UKP to \(\mathcal {O}{(n + \frac {1}{\varepsilon ^2} \log ^3(\frac {1}{\varepsilon }) })\) and for UKPIP to \(\mathcal {O}{(n \log M \!+ \! M \frac {1}{\varepsilon } \log \frac {1}{\varepsilon } \!+ \! \min \{ \lfloor \log \frac {1}{c_{\min }} \rfloor \!+ \! 1, M \} \frac {1}{\varepsilon ^2} \log ^3 \frac {1}{\varepsilon } \!+ \! \min \{ \lfloor \log \frac {1}{c_{\min }} \rfloor \!+ \! 1, M \} \cdot n }\)). This improves the running time of the AFPTAS for Bin Packing to \(\mathcal {O}{(\frac {1}{\varepsilon ^5} \log ^4 \frac {1}{\varepsilon } + \log (\frac {1}{\varepsilon }) n}\)) and the AFPTAS for VBP to \(\mathcal {O}({\frac {1}{\varepsilon ^5} \log ^5 \frac {1}{\varepsilon } + M + \log (\frac {1}{\varepsilon }) n}\)). The first result can be found on arXiv: http://​arXiv.​org/​abs/​1504.​04650. The second result will be published in the PhD thesis of Stefan Kraft. Moreover, Hoberg and Rothvoß have proved that we have \(OPT(I) \leq LIN(I) + \mathcal {O}{(\log LIN(I)})\) for Bin Packing (see arXiv: http://​arXiv.​org/​abs/​1503.​08796).