×

Some remarks on a paper by W. Knödel on the mean behaviour of online bin packing algorithms. (Einige Bemerkungen zu einer Arbeit von W. Knödel über das mittlere Verhalten von on-line-Packungsalgorithmen.) (German) Zbl 0557.68047

Summary: For the bin packing algorithms best fit and first fit W. Knödel [ibid. 19, 427–433 (1983)] has considered the average density of packing assuming stochastic input sequence. Essentially it is described asymptotically by \(8c e^{-1/6}\sqrt{n/\pi}/9\) (\(c\) a numerical constant). In the present note the value \(c=e^{1/6}\sqrt{3}/2\) is determined. By means of the trinomial coefficients the average can be computed exactly.

MSC:

68W27 Online algorithms; streaming algorithms
68R05 Combinatorics in computer science
PDFBibTeX XMLCite