Paper Info
Title
Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing
Abstract
Abstract: We study the average case performance of the Best Fitalgorithm for on-line bin packing under the distribution Ufj; kg, in which the item sizes are uniformly distributedin the discrete range f1=k; 2=k; : : :; j=kg. Ourmain result is that, in the case j = k \Gamma 2, the expectedwaste for an infinite stream of items remains bounded.This settles an open problem posed recently by Coffmanet al [4]. It is also the first result which involves a detailedanalysis of the infinite...
Year
DOI
Venue
1998
10.1006/jagm.1997.0919
Journal of Algorithms
Keywords
DocType
Volume
random walk,lyapunov function,best fit bin packing,stochastic analysis,data structures,algorithms,evolutionary biology
Journal
27
Issue
ISSN
ISBN
2
0196-6774
0-89871-366-8
Citations 
PageRank 
References 
15
1.51
6
Authors
3
Name
Order
Citations
PageRank
Claire Kenyon1151.51
Yuval Rabani22265274.98
Alistair Sinclair31506308.40