Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

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.
Fichier principal
Vignette du fichier
RR1995-14.pdf (246.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102057 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102057 , version 1

Citer

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⟩
8 Consultations
186 Téléchargements

Partager

Gmail Facebook X LinkedIn More