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

Publication series

Name
PublisherSpringer

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
Faigle, U. ; Kern, Walter. / Packing a bin on-line to maximize the total number of items. Operations Research 1996. Springer-Verlag, Berlin : Springer, 1997. pp. 61-65
@inproceedings{4c0c5187742840fb8ea8b81422bf9692,
title = "Packing a bin on-line to maximize the total number of items",
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.",
keywords = "METIS-141655, IR-85181",
author = "U. Faigle and Walter Kern",
year = "1997",
month = "1",
day = "14",
doi = "10.1007/978-3-642-60744-8_12",
language = "Undefined",
isbn = "3-540-62630-1",
publisher = "Springer",
pages = "61--65",
booktitle = "Operations Research 1996",

}

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

Packing a bin on-line to maximize the total number of items. / Faigle, U.; Kern, Walter.

Operations Research 1996. Springer-Verlag, Berlin : Springer, 1997. p. 61-65.

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

TY - GEN

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

AU - Faigle, U.

AU - Kern, Walter

PY - 1997/1/14

Y1 - 1997/1/14

N2 - 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.

AB - 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.

KW - METIS-141655

KW - IR-85181

U2 - 10.1007/978-3-642-60744-8_12

DO - 10.1007/978-3-642-60744-8_12

M3 - Conference contribution

SN - 3-540-62630-1

SP - 61

EP - 65

BT - Operations Research 1996

PB - Springer

CY - Springer-Verlag, Berlin

ER -

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