Bin packing as a random walk: A note on Knödel's paper (Q1084021)

We study the asymptotic expected behavior of the FF (first-fit) bin packing algorithm for special stochastic input sequences. It is shown that \(FF(L)-OPT(L)=O(\sqrt{n})\) if the items of \(L=(a_ 1,a_ 2,...,a_ n)\) are the following: \(a_ i=b\) with probability 0.5, \(a_ i=1-b\) with probability 0.5. This makes the corresponding result of \textit{W. Knödel} [Elektron. Informationsverarbeitung Kybernetik 19, 427-433 (1983)] more precise.