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

Abstract

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
PublisherSpringer
Pages61-65
Number of pages5
ISBN (Print)3-540-62630-1
DOIs
Publication statusPublished - 14 Jan 1997
Event21th International Symposium on Operations Research, SOR 1996 - Technical University of Braunschweig, Braunschweig, Germany
Duration: 3 Sep 19965 Sep 1996
Conference number: 21

Publication series

Name
PublisherSpringer

Conference

Conference21th International Symposium on Operations Research, SOR 1996
Abbreviated titleSOR
CountryGermany
CityBraunschweig
Period3/09/965/09/96
OtherSeptember 3-6, 1996

Keywords

  • METIS-141655
  • IR-85181

Cite this

Faigle, U., & Kern, W. (1997). Packing a bin on-line to maximize the total number of items. In Operations Research 1996 (pp. 61-65). Springer-Verlag, Berlin: Springer. https://doi.org/10.1007/978-3-642-60744-8_12