Back to University of Twente portal
Packing a bin online to maximize the total number of items
Faigle, Ulrich and Kern, Walter (1996) Packing a bin online to maximize the total number of items. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 455Kb |
| 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 |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 141171