Best-fit bin-packing with random order - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

Best-fit bin-packing with random order

(1)
1

Résumé

Best-fit is the best known algorithm for on-line bin-packing, in the sense that no algorithm is known to behave better both in the worst case (when Best-fit has performance ratio 1.7) and in the average uniform case, with items drawn uniformly in the interval [ 0, 1]. In practical applications, Best-fit appears to perform within a few percent of optimal. In this paper, we study the expected performance ratio, taking the worst-case multiset of items L$, and assuming that the elements of L are inserted in random order, with all permutations equally likely. We show a lower bound of 1.07... and an upper bound of 1.5 on the random order performance ratio of Best-fit. The upper bound contrasts with the result that in the worst case, any (deterministic or randomized) on-line bin-packing algorithm has performance ratio at least 1.54....
L'algorithme de meilleur choix est le meilleur pour la mise en boîte en-ligne, en ce sens qu'on ne connaît pas d'algorithme qui lui est supérieur à la fois dans le pire cas et dans le cas moyen uniforme. En pratique, Meilleur choix semble être à quelques pour cent de l'optimum. Dans cet article, nous étudions la performance relative moyenne par rapport à l'optimum, considérant le pire cas de valeurs de données mais supposant que leur ordre d'arrivée est aléatoire. Nous montrons une borne inférieure de 107 % et une borne supérieure de 150 % à la performance de Meilleur choix avec cette définition.
Fichier principal
Vignette du fichier
RR1995-19.pdf (178.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102019 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102019 , version 1

Citer

Claire Kenyon. Best-fit bin-packing with random order. [Research Report] LIP RR-1995-19, Laboratoire de l'informatique du parallélisme. 1995, 2+12p. ⟨hal-02102019⟩
17 Consultations
381 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More