A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L)+1, ■L FOR THE FFD BIN-PACKING ALGORITHM

<正> The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.