##
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**