On-line maximizing the number of items packed in variable-sized bins
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...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2003
|
| Sorozat: | Acta cybernetica
16 No. 1 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12709 |
| LEADER | 01351nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta12709 | ||
| 005 | 20220614151711.0 | ||
| 008 | 161015s2003 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Epstein Leah | |
| 245 | 1 | 0 | |a On-line maximizing the number of items packed in variable-sized bins |h [elektronikus dokumentum] / |c Epstein Leah |
| 260 | |c 2003 | ||
| 300 | |a 57-66 | ||
| 490 | 0 | |a Acta cybernetica |v 16 No. 1 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 700 | 0 | 1 | |a Favrholdt Lene M. |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12709/1/cybernetica_016_numb_001_057-066.pdf |z Dokumentum-elérés |