摘要
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.
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.
