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

U. Faigle; Walter Kern

doi:10.1007/978-3-642-60744-8_12

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

U. Faigle, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	Undefined
Title of host publication	Operations Research 1996
Place of Publication	Springer-Verlag, Berlin
Publisher	Springer
Pages	61-65
Number of pages	5
ISBN (Print)	3-540-62630-1
DOIs	https://doi.org/10.1007/978-3-642-60744-8_12
Publication status	Published - 14 Jan 1997
Event	21th Symposium on Operations Research, SOR 1996 - Technical University of Braunschweig, Braunschweig, Germany Duration: 3 Sept 1996 → 5 Sept 1996 Conference number: 21

Publication series

Name
Publisher	Springer

Conference

Conference	21th Symposium on Operations Research, SOR 1996
Abbreviated title	SOR
Country/Territory	Germany
City	Braunschweig
Period	3/09/96 → 5/09/96
Other	September 3-6, 1996

Keywords

METIS-141655
IR-85181

Access to Document

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

Cite this

@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 = jan,

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",

address = "Germany",

note = "21th Symposium on Operations Research, SOR 1996 ; Conference date: 03-09-1996 Through 05-09-1996",

}

TY - GEN

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

AU - Faigle, U.

AU - Kern, Walter

N1 - Conference code: 21

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

T2 - 21th Symposium on Operations Research, SOR 1996

Y2 - 3 September 1996 through 5 September 1996

ER -