On-line maximizing the number of items packed in variable-sized bins

Epstein Leah and Favrholdt Lene M.: On-line maximizing the number of items packed in variable-sized bins. In: Acta cybernetica, (16) 1. pp. 57-66. (2003)

[thumbnail of cybernetica_016_numb_001_057-066.pdf]
Cikk, tanulmány, mű

Download (916kB) | Preview


We study an on-line bin packing problem. A fixed number n of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3 and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/2n-1.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2003
Volume: 16
Number: 1
ISSN: 0324-721X
Page Range: pp. 57-66
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38515/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 65-66. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 14. 15:17
URI: http://acta.bibl.u-szeged.hu/id/eprint/12709

Actions (login required)

View Item View Item