Best-fit bin-packing with random order

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