Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin packing case study

E.G. Coffman, Jr, C. Coucoubetis, M.R. Garey, D.S. Johnson, L.A. McGeoch, P.W. Shor, R.R. Weber, and M. Yannakakis. In Proc. 23 Annual ACM Symposium on Theory of Computing, New Orleans, May 6-8, pages 230-240, 1991.

Abstract

We consider the average case behavior of one-dimensional bin packing algorithms
in the case where bins have unit capacity and item sizes are chosen according to
the ``discrete uniform'' distribution $U\{j,k\}$, $1\leq j^\leq k$, where each
item size in the set $\{1/k,2/k,\ldots,j/k\}$ has probability $1/j$ of being
chosen.  Note that for fixed $j,k$ the distributions $U\{mj,mk\}$ approach the
continuous distribution $U(0,j/k]$ as $m\rightarrow\infty$, where in $U(0,j/k]$
the item sizes are chosen uniformly from the half-open interval $(0,j/k]$.  In
this paper, we show that average case behavior can differ substantially under
the two types of distributions.  We show that for all $j,k$, $j< k-1$, there
exist on-line algorithms that have constant expected waste under $U\{j,k\}$,
whereas no on-line algorithm can have less than $\Omega(n^{1/2})$ waste under
$U(0,u]$ for any $u\leq 1$.  Contrariwise, although the First Fit Decreasing
(off-line) algorithm has constant expected waste under $U(0,u]$ for all 
$u\leq 1/2$, there are many combinations $j,k$ with $j<k/2$ such that First
Fit Decreasing has $\Theta(n)$ expected waste under $U\{j,k\}$.  The constant of
proportionality is maximized for $j=6$ and $k=13$, in which case the expected
waste is $n/624$.

back to list of papers