@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 = "University of Twente",

number = "1330",

address = "Netherlands",

}