A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L) 1, ■L FOR THE FFD BIN-PACKING ALGORITHM |
| |
引用本文: | 越民义.A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L) 1, ■L FOR THE FFD BIN-PACKING ALGORITHM[J].应用数学学报(英文版),1991(4). |
| |
作者姓名: | 越民义 |
| |
作者单位: | Institute of |
| |
摘 要: | 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.
|
本文献已被 CNKI 等数据库收录! |
|