Packing a bin on-line to maximize the total number of items

U. Faigle, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


A bin of capacity 1 and a finite sequence σ of items of sizes a1,a2,… are considered, where the items are given one by one without information about the future. An online algorithm A must irrevocably decide whether or not to put an item into the bin whenever it is presented. The goal is to maximize the number of items collected. A is f-competitive for some function f if n*(σ) ≤ f(nA(σ)) holds for all sequences σ, where n* is the (theoretical) optimum and nA the number of items collected by A. A necessary condition on f for the existence of an f-competitive (possibly randomized) online algorithm is given. On the other hand, this condition is seen to guarantee the existence of a deterministic online algorithm that is “almost” f-competitive in a well-defined sense.
Original languageUndefined
Title of host publicationOperations Research 1996
Place of PublicationSpringer-Verlag, Berlin
Number of pages5
ISBN (Print)3-540-62630-1
Publication statusPublished - 14 Jan 1997
Event21th Symposium on Operations Research, SOR 1996 - Technical University of Braunschweig, Braunschweig, Germany
Duration: 3 Sept 19965 Sept 1996
Conference number: 21

Publication series



Conference21th Symposium on Operations Research, SOR 1996
Abbreviated titleSOR
OtherSeptember 3-6, 1996


  • METIS-141655
  • IR-85181

Cite this