Menu
Given \(m\) unit-capacity bins and a collection \(x(n)\) of \(n\) pieces, each with a positive size at most one, the dual bin packing problem asks for packing a maximum number of pieces into the \(m\) bins so that no bin capacity is
exceeded. Motivated by the NP-hardness of the problem, Coffman et al. proposed a class of heuristics, the \emph{prefix} algorithms, and analyzed its worst-case performance bound.
Bruno and Downey gave a probabilistic bound for the FFI algorithm (which is a prefix algorithm proposed by Coffman et al.), under the assumption that piece sizes are drawn from the uniform distribution over \([0, 1]\). In this article, we generalize their result: Let \(F\) be an \emph{arbitrary} distribution over \([0, 1]\), and let
\(x(n)\) denote a random sample of a random variable \(X\) distributed according to \(F\). Then, for any \(\varepsilon > 0\), there are \(\lambda > 0\) and \(N > 0\),
dependent only on \(m\), \(\varepsilon\), and \(F\), such that for all \(n \geq N\),
\begin{align*}
\Pr\left(\frac{{\mathrm{OPT}}(x(n), m)}{{\mathrm{PRE}}(x(n), m)} \leq 1 + \varepsilon\right)
&> 1 – Me^{-2\lambda n},
\end{align*}
where \(M\) is a universal constant.
Another probabilistic bound is also given for \(\frac{\mathrm{OPT}(x(n),m)}{\mathrm{PRE}(x(n),m)}\), under a
mild assumption of \(F\).