Packing a bin online to maximize the total number of items

Share/Save/Bookmark

Faigle, Ulrich and Kern, Walter (1996) Packing a bin online to maximize the total number of items. [Report]

open access
[img]
Preview
PDF
466kB
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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/30531
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141171