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 :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102019
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:09 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:39 AM

File

RR1995-19.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102019, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

36