Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing

Nous \'etudions l'algorithme ``Meilleur choix'' pour le probl\`eme de la mise en bo\^\i tes en-ligne, lorsque les donn\'ees sont tir\'ees de fa\c con al\'eatoire uniforme dans l'ensemble $\{1/k,2/k,\ldots,j/k\}$. Notre r\'esultat principal est que, dans le cas $j=k-2$, l'espace moyen perdu reste asymptotiquement born\'e. Ceci r\'esoud un probl\`emede Coffman et al., et utilise une analyse d\'etaill\'ee de la cha\^\i ne de Markov infinie multi-dimensionnelle sous-jacente \`a l'algorithme. Travail en collaboration avec Yuval Rabani et Alistair Sinclair.