On-Line Bin Packing in Linear Time.

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 algorithm's performance involves a novel use of weighting functions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1983
Accession Number
ADA142365

Entities

People

  • D. J. Brown
  • P. Ramanan

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Illinois
  • Information Processing
  • Intervals
  • Military Research
  • New York
  • Security
  • Two Dimensional
  • Universities
  • Weighting Functions

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Materials Science and Engineering.
  • Radar Systems Engineering.