Online Bandwidth packing with symmetric distribution - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2007

Online Bandwidth packing with symmetric distribution

Marc Lelarge
  • Fonction : Auteur
  • PersonId : 833445

Résumé

We consider the following stochastic bin packing process: the items arrive continuously over time to a server and are packed into bins of unit size according to an online algorithm. The unpacked items form a queue. The items have random sizes with symmetric distribution. Our first contribution identifies some monotonicity properties of the queueing system that allow to derive bounds on the queue size for First Fit and Best Fit algorithms. As a direct application, we show how to compute the stability region under very general conditions on the input process. Our second contribution is a study of the queueing system under heavy load. We show how the monotonicity properties allow one to derive bounds for the speed at which the stationary queue length tends to infinity when the load approaches one. In the case of Best Fit, these bounds are tight. Our analysis shows connections between our dynamic model, average-case results on the classical bin packing problem and planar matching problems.
Fichier principal
Vignette du fichier
dmAH0136.pdf (195.7 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184778 , version 1 (17-08-2015)

Identifiants

Citer

Marc Lelarge. Online Bandwidth packing with symmetric distribution. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.519-532, ⟨10.46298/dmtcs.3530⟩. ⟨hal-01184778⟩
126 Consultations
507 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More