Packing a bin online to maximize the total number of items

U. Faigle, Walter Kern

Research output: Book/ReportReportProfessional

42 Downloads (Pure)

Abstract

A bin of capacity 1 and a nite 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-dened sense.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages10
ISBN (Print)0169-2690
Publication statusPublished - 1996

Publication series

NameMemorandum / Faculty of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
No.1330

Keywords

  • METIS-141171
  • IR-30531

Cite this

Faigle, U., & Kern, W. (1996). Packing a bin online to maximize the total number of items. (Memorandum / Faculty of Applied Mathematics; No. 1330). Enschede: Universiteit Twente.
Faigle, U. ; Kern, Walter. / Packing a bin online to maximize the total number of items. Enschede : Universiteit Twente, 1996. 10 p. (Memorandum / Faculty of Applied Mathematics; 1330).
@book{4c62870a9d81459396ab9a7122cd65c4,
title = "Packing a bin online to maximize the total number of items",
abstract = "A bin of capacity 1 and a nite 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-dened sense.",
keywords = "METIS-141171, IR-30531",
author = "U. Faigle and Walter Kern",
note = "Memorandum fac. TW",
year = "1996",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum / Faculty of Applied Mathematics",
publisher = "Universiteit Twente",
number = "1330",

}

Faigle, U & Kern, W 1996, Packing a bin online to maximize the total number of items. Memorandum / Faculty of Applied Mathematics, no. 1330, Universiteit Twente, Enschede.

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

Enschede : Universiteit Twente, 1996. 10 p. (Memorandum / Faculty of Applied Mathematics; No. 1330).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - Faigle, U.

AU - Kern, Walter

N1 - Memorandum fac. TW

PY - 1996

Y1 - 1996

N2 - A bin of capacity 1 and a nite 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-dened sense.

AB - A bin of capacity 1 and a nite 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-dened sense.

KW - METIS-141171

KW - IR-30531

M3 - Report

SN - 0169-2690

T3 - Memorandum / Faculty of Applied Mathematics

BT - Packing a bin online to maximize the total number of items

PB - Universiteit Twente

CY - Enschede

ER -

Faigle U, Kern W. Packing a bin online to maximize the total number of items. Enschede: Universiteit Twente, 1996. 10 p. (Memorandum / Faculty of Applied Mathematics; 1330).