On-Line Bin Packing in Linear Time.
ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP
Pagination or Media Count:
This paper studies the one-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. The authors present a new linear-time algorithm, the Modified Harmonic Algorithm. The analysis of the algorithms performance involves a novel use of weighting functions.
- Statistics and Probability