A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms.

Abstract

This paper is concerned with algorithms for which the pieces (numbers) in list L are available one at a time, and each piece must be placed in some bin before the next piece is available; such an algorithm is referred to as on-line. The performance measure used is the ratio of the number of bins used by an algorithm A in packing list L, A(L), to the optimum (minimum) number of bins required to pack the list, OPT(L).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1979
Accession Number
ADA085315

Entities

People

  • Donna J. Brown

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Electrical Engineering
  • Electronics
  • Engineering
  • Equations
  • Governments
  • Illinois
  • Inequalities
  • National Governments
  • Numbers
  • Real Numbers
  • Two Dimensional
  • United States
  • United States Government

Readers

  • Graph Algorithms and Convex Optimization.
  • Materials Science