Résumés
Abstract
We study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items a1, a2, . . . , an and a sequence of their sizes (s1, s2, . . . , sn) (each size si ∈ (0, 1]) and are required to pack the items into a minimum number of unit-capacity bins. Let R1{ , } be the minimal asymptotic competitive ratio of an on-line algorithm in the case when all items are only of two different sizes α and β. We prove that max{R1{ , } : α, β ∈ (0, 1]} = 4/3. We also obtain an exact formula for R1{ , } when max{α, β} > 12 . This result extends the result of Faigle, Kern and Turan (1989) that R1{ , } = 43 for β = 12 − ǫ and α = 12 + ǫ for any fixed nonnegative ǫ < 16 .
Keywords:
- On-line algorithms,
- bin packing,
- competitive ratio
Veuillez télécharger l’article en PDF pour le lire.
Télécharger