Abstract
In the bin packing problem, a list L of n items is to be packed into a
sequence of unit capacity bins with the goal of minimizing the number
of bins used. First Fit (FF) is one of the most natural on-line
algorithms for this problem, based on the simple rule that each
successive item is packed into the first bin of the sequence that
currently has room for it. We present an average-case analysis of FF in
the discrete uniform model: the item sizes are drawn independently and
uniformly at random from the set f{1/k,...,j/k} for some k>1. Let
W^FF (L) denote the wasted space in the FF packing of L, i.e., the
total space still available in the occupied bins. We prove that E[W^FF
(L)] = O(\sqrt{nk}), i.e., there exists a constant c>0 such that
E[W^FF (L)] < c\sqrt{nk} for all n,k sufficiently large. By a
complementary lower bound argument, we prove that this result is
sharp, unless k is allowed to grow withn at a rate faster than
n^{1/3}, in which case E[W^FF(L)] = Theta(n^{2=3}). Finally, we show
that this last result carries over to the continuous uniform model,
where item sizes are chosen uniformly from [0,1]. The O(n^{2=3}) upper
bound for the continuous model is new and solves a problem posed a
decade ago. The proofs of many of these results require extensions to
the theory of stochastic planar matching.