Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Best-fit bin-packing with random order

Abstract : 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....
Document type :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:12:09 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM


Files produced by the author(s)


  • HAL Id : hal-02102019, version 1



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⟩



Record views


Files downloads