Best-fit decreasing is the offline bin-packing algorithm in which items are first sorted in decreasing order of size, and then an item is packed into the bin with the smallest possible remaining space. This paper studies the number Bn of bins required, under the probability model in which item sizes are independent and uniformly distributed on [0,1]. The authors show that n - ½ ( Bn - n &slash; 2 ) converges in distribution but, surprisingly, the limit is not normal. The method consists of studying patterns created by the algorithm.
