Accession Number:

ADA142365

Title:

On-Line Bin Packing in Linear Time.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1983-10-01

Pagination or Media Count:

28.0

Abstract:

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE