Online Bandwidth packing with symmetric distribution

Marc Lelarge 1
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : 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.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.519-532, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184778
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:16
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:15:49

Fichier

dmAH0136.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184778, version 1

Collections

Citation

Marc Lelarge. Online Bandwidth packing with symmetric distribution. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.519-532, 2007, DMTCS Proceedings. 〈hal-01184778〉

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

133