Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing.

Abstract : We study of the average case performance of the Best Fit algorithm for on-line bin packing under the distribution in which the item sizes are uniformly distributed in the discrete range{1/k,2/k,...,j/k}. Our main result is that, in the case j=k-2, the expected waste for an infinite stream of items remains bounded. This settles an open problem posedrecently by Coffman et al. It is also the first result which involves a detailed analysis of the infinite multi-dimensional Markov chain underlying the algorithm.
Document type :
Reports
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102057
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:13:07 AM
Last modification on : Saturday, May 4, 2019 - 1:26:36 AM

File

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

Identifiers

  • HAL Id : hal-02102057, version 1

Collections

Citation

Claire Kenyon, Yuval Rabani, Alistair Sinclair. Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing.. [Research Report] LIP RR-1995-14, Laboratoire de l'informatique du parallélisme. 1995, 2+19p. ⟨hal-02102057⟩

Share

Metrics

Record views

9

Files downloads

39