Bounded space on-line variable-sized bin packing

In this paper we consider the fc-bounded space on-line bin packing problem. Some efficient approximation algorithms are described and analyzed. Selecting either the smallest or the largest available bin size to start a new bin as items arrive turns out to yield a worst-case performance bound of 2. B...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Burkard Rainer E.
Zhang Guochuan
Dokumentumtípus: Cikk
Megjelent: 1997
Sorozat:Acta cybernetica 13 No. 1
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12579
Leíró adatok
Tartalmi kivonat:In this paper we consider the fc-bounded space on-line bin packing problem. Some efficient approximation algorithms are described and analyzed. Selecting either the smallest or the largest available bin size to start a new bin as items arrive turns out to yield a worst-case performance bound of 2. By packing large items into appropriate bins, an efficient approximation algorithm is derived from fc-bounded space on-line bin packing algorithms and its worst-case performance bounds is 1.7 for k > 3.
Terjedelem/Fizikai jellemzők:63-76
ISSN:0324-721X