Geodesic
Online Bandwidth packing with symmetric distribution
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2007_special_253_a12,
     author = {Lelarge, Marc},
     title = {Online {Bandwidth} packing with symmetric distribution},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3530},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3530/}
}
TY  - JOUR
AU  - Lelarge, Marc
TI  - Online Bandwidth packing with symmetric distribution
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3530/
DO  - 10.46298/dmtcs.3530
LA  - en
ID  - DMTCS_2007_special_253_a12
ER  - 
%0 Journal Article
%A Lelarge, Marc
%T Online Bandwidth packing with symmetric distribution
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3530/
%R 10.46298/dmtcs.3530
%G en
%F DMTCS_2007_special_253_a12
Lelarge, Marc. Online Bandwidth packing with symmetric distribution. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3530. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3530/

Cité par Sources :