Bin packing can be solved within 1 + ε in linear time |
| |
| Authors: | W. Fernandez de la Vega G. S. Lueker |
| |
| Affiliation: | (1) C. N. R. S., 54 Bd. Raspail, 75 006 Paris, France;(2) Dept. Info. Comp. Sci., Univ. of California, 92 717 Irvine, CA, U.S.A.;(3) Present address: 4 bis rue Wulfran Puget, 13 008 Marseille, France |
| |
| Abstract: | For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997. |
| |
| Keywords: | 68 C 25 68 E 05 90 C 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
