Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing.
Résumé
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.
Nous étudions l'algorithme "Meilleur choix" pour le problème de la mise en boîtes en-ligne lorsque les données sont tirées de façon aléatoire uniforme dans l'ensemble {1/k, 2/k, ..., j/k}. Notre résultat principal est que, dans le cas j = k - 2, l'espace moyen perdu reste asymptotiquement borné. Ceci résoud un problème de Coffman et al. , et utilise une analyse détaillée de la chaîne de Markov infinie multi-dimensionnelle sous-jacente à l'algorithme.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...