Asgeirsson Eyjólfur Ingi; Ayesta U.; Coffman E.; Etra J.; Momčilović P.; Phillips D.; Vokhshoori V.; Wang Z.; Wolfe J.: Closed on-line bin packing. In: Acta cybernetica, (15) 3. pp. 361-367. (2002)
Előnézet |
Cikk, tanulmány, mű
cybernetica_015_numb_003_361-367.pdf Letöltés (616kB) | Előnézet |
Absztrakt (kivonat)
An optimal algorithm for the classical bin packing problem partitions (packs) a given set of items with sizes at most 1 into a smallest number of unit-capacity bins such that the sum of the sizes of the items in each bin is at most 1. Approximation algorithms for this NP-hard problem are called on-line if the items are packed sequentially into bins with the bin receiving a given item being independent of the number and sizes of all items as yet unpacked. Off-line algorithms plan packings assuming full (advance) knowledge of all item sizes. The closed on-line algorithms are intermediate: item sizes are not known in advance but the number n of items is. The uniform model, where the n item sizes are independent uniform random draws from [0,1], commands special attention in the average-case analysis of bin packing algorithms. In this model, the expected wasted space produced by an optimal off-line algorithm is Θ(√n), while that produced by an optimal on-line algorithm is Θ(√n log n)- Surprisingly, an optimal closed on-line algorithm also wastes only s Θ(√n) space on the average. A proof of this last result is the principal contribution of this paper. However, we also identify a class of optimal closed algorithms, extend the main result to other probability models, and give an estimate of the hidden constant factor.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2002 |
| Kötet: | 15 |
| Szám: | 3 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 361-367 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38513/ |
| Kulcsszavak: | Számítástechnika, Kibernetika, Algoritmus |
| Megjegyzések: | Bibliogr.: p. 366-367. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2016. okt. 15. 12:25 |
| Utolsó módosítás: | 2022. jún. 14. 13:32 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12684 |
 |
Tétel nézet |
