General Probabilistic Bounds for Dual Bin Packing Heuristics

Abstract

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 $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 $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 $\epsilon >0$, there are $\lambda >0$ and $N>0$,
dependent only on $m$, $\epsilon$, and $F$, such that for all $n\ge N$,
$$\begin{array}{rl}Pr(\frac{\mathrm{O}\mathrm{P}\mathrm{T}(x(n),m)}{\mathrm{P}\mathrm{R}\mathrm{E}(x(n),m)}\le 1+\epsilon )& >1–M{e}^{-2\lambda n},\end{array}$$
where $M$ is a universal constant.
Another probabilistic bound is also given for $\frac{\mathrm{O}\mathrm{P}\mathrm{T}(x(n),m)}{\mathrm{P}\mathrm{R}\mathrm{E}(x(n),m)}$, under a
mild assumption of $F$.