BIN PACKING WITH DISCRETE ITEM SIZES .2. TIGHT BOUNDS ON FIRST FIT

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 algor ithms for this problem, based on the simple rule that each successive item is packed into the first bin of the sequence that currently has r oom 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 {1/k,...,(k-1)/k}, for some k>1. Let W-FF(L) deno te the wasted space in the FF packing of L, i.e., the total space stil l available in the occupied bins. We prove that E[W-FF(L)] = O(root nk ), i.e., there exists a constant c>0 such that E[W-FF(L)]less than or equal to c root 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 with n 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 carrie s over to the continuous uniform model, where item sizes are chosen un iformly 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 m atching. (C) 1997 John Wiley & Sons, Inc.